Counting the Number of Crossings in Geometric Graphs
A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an O(n2log n) time algorithm to compute the number of pairs of edges that cross in a geometric graph on n vertices. For layered...
- Autores:
-
Duque Patiño, Frank Rodrigo
Fabila Monroy, Ruy
Hernández Vélez, César
Hidalgo Toscano, Carlos
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2021
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/46182
- Acceso en línea:
- https://hdl.handle.net/10495/46182
- Palabra clave:
- Algoritmos
Algorithms
Teoría de grafos
Graph theory
Grafo geométrico
Número de cruce rectilíneo
Geometric graph
Rectilinear crossing number
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by-nc-nd/4.0/
| Summary: | A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an O(n2log n) time algorithm to compute the number of pairs of edges that cross in a geometric graph on n vertices. For layered graphs and convex geometric graphs the algorithm takes O(n2) time. |
|---|