Computing the Girth of a Segment Intersection Graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912978415124480 |
|---|---|
| author | Chan, Timothy M. Yu, Yuancheng |
| author_facet | Chan, Timothy M. Yu, Yuancheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21585 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing the Girth of a Segment Intersection Graph Chan, Timothy M. Yu, Yuancheng Computational Geometry 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. |
| title | Computing the Girth of a Segment Intersection Graph |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.21585 |