Counting the Number of Crossings in Geometric Graphs
Frank Duque, Fabila Monroy, Ruy, César Hernández-Vélez, Carlos Hidalgo-Toscano · Institutional Repository University of Antioquia (University of Antioquia) · 2021
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.