Counting the Number of Crossings in Geometric Graphs

04/24/2019
by   Frank Duque, et al.
0

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^2 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^2) time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset