2026-07-23T06:18:10Z https://drops.dagstuhl.de/oai

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

A WSPD, Separator and Small Tree Cover for c-Packed Graphs Deryckere, Lindsey Gudmundsson, Joachim van Renssen, André Sha, Yuan Wong, Sampson Well-separated pair decomposition separator tree cover distance oracles realistic graphs The c-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in c-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the c-packedness assumption, and more specifically, on c-packed graphs. In this paper, we prove two fundamental properties of c-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lindsey Deryckere and Joachim Gudmundsson and André van Renssen and Yuan Sha and Sampson Wong 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.21 urn:nbn:de:0030-drops-242529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode