Charting the landscape of diameter computation on geometric intersection graphs in the plane Chan, Timothy M. ; https://orcid.org/0000-0002-8093-0675 Chang, Hsien-Chih ; https://orcid.org/0000-0001-6714-7988 Gao, Jie ; https://orcid.org/0000-0001-5083-6082 Kisfaludi-Bak, Sándor ; https://orcid.org/0000-0002-6856-2902 Le, Hung ; https://orcid.org/0000-0001-8223-9944 Zheng, Da Wei String graphs Fine-grained complexity Theory of computation → Computational geometry ddc:000 Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: 1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/22405 https://research-explorer.ista.ac.at/download/22405/22407 Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape of diameter computation on geometric intersection graphs in the plane. In: <i>53rd International Colloquium on Automata, Languages, and Programming</i>. Vol 374. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2026.54">10.4230/LIPICS.ICALP.2026.54</a> eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPICS.ICALP.2026.54 info:eu-repo/semantics/altIdentifier/e-issn/1868-8969 info:eu-repo/semantics/altIdentifier/e-issn/9783959774284 info:eu-repo/semantics/altIdentifier/arxiv/2605.10692 info:eu-repo/semantics/openAccess