Counting the Number of Crossings in Geometric Graphs

2019/04/24 by Duque, Frank, Fabila-Monroy, Ruy, Hernández-Vélez, César +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1904.11037

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(n² log n) algorithm to compute the number of pairs of edges that cross in a geometric graph on n points. For layered, and convex geometric graphs the algorithm takes O(n²) time.

Related

• Counting and Enumerating Crossing-free Geometric Graphs
• Computing Crossing Numbers in Quadratic Time
• A Note on the k-colored Crossing Ratio of Dense Geometric Graphs
• On the Maximum Crossing Number
• On disjoint crossing families in geometric graphs