An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Oscar E. García-Quintero, Carlos Hidalgo-Toscano

Research output: Contribution to journalArticlepeer-review


A drawing of a graph in the plane is pseudolinear if the edges of the drawing can be extended to doubly-infinite curves that form an arrange-ment of pseudolines, that is, any pair of these curves crosses precisely once. A special case is rectilinear drawings where the edges of the graph are drawn as straight line segments. The rectilinear (pseudolinear) crossing number of a graph is the minimum number of pairs of edges of the graph that cross in any of its rectilinear (pseudolinear) drawings. In this paper we describe an ongoing project to continuously obtain better asymptotic upper bounds on the rectilinear and pseudolinear crossing number of the complete graph K n.

Original languageEnglish
Pages (from-to)421-432
Number of pages12
JournalJournal of Graph Algorithms and Applications
Issue number3
Publication statusPublished - 1 Jan 2020

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computer Science(all)
  • Computer Science Applications
  • Computational Theory and Mathematics

Fields of Expertise

  • Information, Communication & Computing

Cite this