2026-09-05T11:57:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25836 2026-06-23T12:59:16Z ddc:004 open_access

Computing the Girth of a Segment Intersection Graph Chan, Timothy M. Yu, Yuancheng Geometric intersection graphs girth shortest paths graph separators matrix multiplication 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-ε}) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Yuancheng Yu 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.30 urn:nbn:de:0030-drops-258364 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode