conference paper published yes Timothy M. Chan author 0000-0002-8093-0675 Hsien-Chih Chang author 0000-0001-6714-7988 Jie Gao author 0000-0001-5083-6082 Sándor Kisfaludi-Bak author 0000-0002-6856-2902 Hung Le author 0000-0001-8223-9944 Da Wei Zheng author af77956b-e859-11ef-8dc9-d301b898e32f MoHe department ICALP: Automata, Languages and Programming Static and Dynamic Hierarchical Graph Decompositions project 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. https://research-explorer.ista.ac.at/download/22405/22407/2026_LIPIcSICALP_Chan.pdf application/pdfno Schloss Dagstuhl – Leibniz-Zentrum für Informatik2026Egham, United Kingdom eng String graphsFine-grained complexityTheory of computation → Computational geometry 1868-8969 9783959774284 2605.1069210.4230/LIPICS.ICALP.2026.54 374 T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “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. <a href="https://doi.org/10.4230/LIPICS.ICALP.2026.54">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>. Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the landscape of diameter computation on geometric intersection graphs in the plane. 53rd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22. T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the landscape of diameter computation on geometric intersection graphs in the plane,” in <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Egham, United Kingdom, 2026, vol. 374. Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” <i>53rd International Colloquium on Automata, Languages, and Programming</i>, vol. 374, 54:1-54:22, 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>. 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> Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). 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). Egham, United Kingdom: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ICALP.2026.54">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a> 224052026-07-27T05:53:08Z2026-07-27T06:22:03Z