Counting the Number of Crossings in Geometric Graphs (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.