Computing the Girth of a Segment Intersection Graph
This addresses an open question in computational geometry for researchers, though it is incremental progress.
The paper tackles the problem of computing the girth of intersection graphs of line segments in the plane, achieving an algorithm with O(n^{1.483}) expected time, which is the first to break the O(n^{3/2}) barrier.
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 with $O(n^{3/2-\varepsilon})$ running time for a positive constant $\varepsilon$, and makes progress towards an open question posed by Chan (SODA 2023). The main techniques include (i)~the usage of recent subcubic algorithms for bounded-difference min-plus matrix multiplication, and (ii)~an interesting variant of the planar graph separator theorem. The result extends to intersection graphs of connected algebraic curves or semialgebraic sets of constant description complexity.