License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.43
URN: urn:nbn:de:0030-drops-144835
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14483/
Go to the corresponding LIPIcs Volume Portal

Ducoffe, Guillaume

Isometric Embeddings in Trees and Their Use in Distance Problems

pdf-format:
LIPIcs-MFCS-2021-43.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ducoffe:LIPIcs.MFCS.2021.43,
  author =	{Ducoffe, Guillaume},
  title =	{{Isometric Embeddings in Trees and Their Use in Distance Problems}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14483},
  URN =		{urn:nbn:de:0030-drops-144835},
  doi =		{10.4230/LIPIcs.MFCS.2021.43},
  annote =	{Keywords: Tree embeddings, Range queries, Centroid decomposition, Heavy-path decomposition, Diameter, Radius and all Eccentricities computations}
}

Keywords: Tree embeddings, Range queries, Centroid decomposition, Heavy-path decomposition, Diameter, Radius and all Eccentricities computations
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI