Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00540
An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
Oswin Aichholzer,
Frank Duque,
Ruy Fabila-Monroy,
Oscar E. GarcĂa-Quintero, and
Carlos Hidalgo-Toscano
Vol. 24, no. 3, pp. 421-432, 2020. Regular paper.
Abstract 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 arrangement 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$.
|
Submitted: July 2019.
Reviewed: January 2020.
Revised: February 2020.
Accepted: July 2020.
Final: July 2020.
Published: July 2020.
Communicated by
William S. Evans
|
Journal Supporters
|