2026-07-23T19:24:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14483 2024-03-06T10:54:07Z ddc:004 open_access

Isometric Embeddings in Trees and Their Use in Distance Problems Ducoffe, Guillaume Tree embeddings Range queries Centroid decomposition Heavy-path decomposition Diameter Radius and all Eccentricities computations We present powerful techniques for computing the diameter, all the eccentricities, and other related distance problems on some geometric graph classes, by exploiting their "tree-likeness" properties. We illustrate the usefulness of our approach as follows: - We propose a subquadratic-time algorithm for computing all eccentricities on partial cubes of bounded lattice dimension and isometric dimension O(n^{0.5-ε}). This is one of the first positive results achieved for the diameter problem on a subclass of partial cubes beyond median graphs. - Then, we obtain almost linear-time algorithms for computing all eccentricities in some classes of face-regular plane graphs, including benzenoid systems, with applications to chemistry. Previously, only a linear-time algorithm for computing the diameter and the center was known (and an Õ(n^{5/3})-time algorithm for computing all the eccentricities). - We also present an almost linear-time algorithm for computing the eccentricities in a polygon graph with an additive one-sided error of at most 2. - Finally, on any cube-free median graph, we can compute its absolute center in almost linear time. Independently from this work, Bergé and Habib have recently presented a linear-time algorithm for computing all eccentricities in this graph class (LAGOS'21), which also implies a linear-time algorithm for the absolute center problem. Our strategy here consists in exploiting the existence of some embeddings of these graphs in either a system or a product of trees, or in a single tree but where each vertex of the graph is embedded in a subset of nodes. While this may look like a natural idea, the way it can be done efficiently, which is our main technical contribution in the paper, is surprisingly intricate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Ducoffe 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.43 urn:nbn:de:0030-drops-144835 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.43 eng https://creativecommons.org/licenses/by/4.0/legalcode