An Ongoing Project to Improve the Rectilinearand the Pseudolinear Crossing Constants
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...
- Autores:
-
Duque Patiño, Frank Rodrigo
Aichholzer, Oswin
Fabila Monroy, Ruy
Hidalgo Toscano, Carlos
García Quintero, Óscar
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2020
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/46369
- Acceso en línea:
- https://hdl.handle.net/10495/46369
- Palabra clave:
- Intersection graph theory
Teoría de grafos de intersección
Teoría de grafos
Graph theory
Grupos de puntos
Groups of points
Constantes Matemáticas
Mathematical constants
Intersection graph theory
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by/4.0/
| Summary: | 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 Kn. |
|---|