abstract

• 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. © 2020 Elsevier B.V.

authors

• Duque F.
• Fabila-Monroy R.
• Hernández Vélez Cesar Israel
• Hidalgo-Toscano C.

publication date

• 2021-01-01

funding provided via

• 253261  Grant
• 265667  Grant
• Horizon 2020 Framework Programme, H2020: 734922  Grant

published in

• Information Processing Letters  Journal

keywords

• Algorithms; Geometric graphs; Graph drawings; Rectilinear crossing number Geometry; Graph algorithms; Graph theory; Convex geometric graphs; Geometric graphs; Layered graphs; Points in general position; Straight-line segments; Time algorithms; Graph structures

Digital Object Identifier (DOI)

• 10.1016/j.ipl.2020.106028

start page

end page

volume

• 165