20.500.12556/RUL-176952 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 Angleški jezik Članek v reviji 2025-12-16 12:43:46 2025-12-16 12:43:47 2025-12-17 04:40:05 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 DDB7EE0A89EECB322B87EAB6F58D8FCA c0ca0dd87f892865e54f50b7acdfb7f07e5956c60ef822d60a528fab467fd3e5 219624a1-da74-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=223793 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.13 1 0c2de1b7-da74-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=223792 Fakulteta za matematiko in fiziko 0 0 0