2026-07-21T12:18:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24244 2025-11-12T13:39:21Z ddc:004 open_access

Algorithms for Distance Problems in Continuous Graphs Cabello, Sergio Garijo, Delia Kalb, Antonia Klute, Fabian Parada, Irene Silveira, Rodrigo I. diameter mean distance continuous graph treewidth planar graph 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²) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergio Cabello and Delia Garijo and Antonia Kalb and Fabian Klute and Irene Parada and Rodrigo I. Silveira 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.13 urn:nbn:de:0030-drops-242446 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode