---
OA_place: publisher
OA_type: gold
_id: '22405'
abstract:
- lang: eng
text: "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]. \r\nWe 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: \r\n1) 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.
\r\n2) 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. \r\n3) 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]. \r\n4) 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."
acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih
Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271,
DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported
by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF
grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project
has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982.
For open access purposes, the author has applied a CC BY public copyright\r\nlicense
to any author-accepted manuscript version arising from this submission.\r\n"
article_number: 54:1-54:22
article_processing_charge: No
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
orcid: 0000-0002-8093-0675
- first_name: Hsien-Chih
full_name: Chang, Hsien-Chih
last_name: Chang
orcid: 0000-0001-6714-7988
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
orcid: 0000-0001-5083-6082
- first_name: Sándor
full_name: Kisfaludi-Bak, Sándor
last_name: Kisfaludi-Bak
orcid: 0000-0002-6856-2902
- first_name: Hung
full_name: Le, Hung
last_name: Le
orcid: 0000-0001-8223-9944
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: '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: 53rd
International Colloquium on Automata, Languages, and Programming. Vol 374.
Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54'
apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the landscape of diameter computation on geometric intersection
graphs in the plane. In 53rd International Colloquium on Automata, Languages,
and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl – Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54'
chicago: 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 53rd International Colloquium on Automata,
Languages, and Programming, Vol. 374. Schloss Dagstuhl – Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54.
ieee: 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 53rd International Colloquium on Automata, Languages, and
Programming, Egham, United Kingdom, 2026, vol. 374.
ista: '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.'
mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on
Geometric Intersection Graphs in the Plane.” 53rd International Colloquium
on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl
– Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54.
short: 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.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'ICALP: Automata, Languages and Programming'
start_date: 2026-07-07
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-27T05:53:08Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-27T06:22:03Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPICS.ICALP.2026.54
external_id:
arxiv:
- '2605.10692'
file:
- access_level: open_access
checksum: 1e66eba4cfe4e74ab28108b1ca0bb956
content_type: application/pdf
creator: dernst
date_created: 2026-07-27T06:20:41Z
date_updated: 2026-07-27T06:20:41Z
file_id: '22407'
file_name: 2026_LIPIcSICALP_Chan.pdf
file_size: 1440497
relation: main_file
success: 1
file_date_updated: 2026-07-27T06:20:41Z
has_accepted_license: '1'
intvolume: ' 374'
keyword:
- String graphs
- Fine-grained complexity
- Theory of computation → Computational geometry
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 53rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eissn:
- 1868-8969
- '9783959774284'
publication_status: published
publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Charting the landscape of diameter computation on geometric intersection graphs
in the plane
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 374
year: '2026'
...