20.500.12556/DiRROS-24740 Algorithms for distance problems in continuous graphs 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. diameter mean distance continuous graphs treewidth planar graphs true false true Angleški jezik Ni določen Neznano 2025-12-16 12:43:43 2025-12-16 12:43:43 2025-12-17 03:58:01 0000-00-00 00:00:00 2025 0 0 Str. 13:1-13:16 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42:519.17 10.4230/LIPIcs.WADS.2025.13 261662723 261608451 LIPIcs.WADS.2025.13.pdf LIPIcs.WADS.2025.13.pdf 1 1579CD8B964FC7804ED311E0CB11A34C 59965d48f762ecaa41454e0733a07f330def6e6e1517075ef5485db676ccaa3f 9bda3878-da74-11f0-94a7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=36971 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.13 1 7c1f0426-da74-11f0-94a7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=36969 Inštitut za matematiko, fiziko in mehaniko 0 0 0