Computing the Girth of a Segment Intersection Graph

Timothy M. Chan, Yuancheng Yu

We present an algorithm that computes the girth of the intersection graph of $n$ given line segments in the plane in $O(n^{1.483})$ expected time. This is the first such algorithm…