Computing the Girth of a Segment Intersection Graph

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(n3/2-ε) running time for a positive constant ε, 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.