Algorithms for distance problems in continuous graphs

Cabello, Sergio (author), Garijo, Delia (author), Kalb, Antonia (author), Klute, Fabian (author), Parada, Irene (author), Silveira, Rodrigo I. (author)

We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with $m$ edges these values can be computed in roughly $O(m^2)$ time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most $k$ can be computed in $O(n \log^{O(k)} n)$ time, where $n$ is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with $n$ vertices and $F$ faces takes $O(n F \log n)$ time.

• Language: English
• Keywords: diameter, mean distance, continuous graphs, treewidth, planar graphs
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: Str. 13:1-13:16
• PID: 20.500.12556/RUL-176952
• UDC: 004.42:519.17
• DOI: 10.4230/LIPIcs.WADS.2025.13
• COBISS.SI-ID: 261662723
• Publication date in RUL: 16.12.2025

Record is a part of a monograph

• Title: 19th International Symposium on Algorithms and Data Structures : WADS 2025, August 11–15, 2025, York University, Toronto, Canada
• Editors: Pat Morin, Eunjin Oh
• Place of publishing: Saarbrücken/Wadern
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Year: 2025
• ISBN: 978-3-95977-398-0
• COBISS.SI-ID: 261608451
• Collection title: Leibniz international proceedings in informatics
• Collection numbering: ǂvol. ǂ349
• Collection ISSN: 1868-8969

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.