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 "treelikeness" properties. We illustrate the usefulness of our approach as follows:
 We propose a subquadratictime 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 lineartime algorithms for computing all eccentricities in some classes of faceregular plane graphs, including benzenoid systems, with applications to chemistry. Previously, only a lineartime 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 lineartime algorithm for computing the eccentricities in a polygon graph with an additive onesided error of at most 2.
 Finally, on any cubefree median graph, we can compute its absolute center in almost linear time. Independently from this work, Bergé and Habib have recently presented a lineartime algorithm for computing all eccentricities in this graph class (LAGOS'21), which also implies a lineartime 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:143:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14483},
URN = {urn:nbn:de:0030drops144835},
doi = {10.4230/LIPIcs.MFCS.2021.43},
annote = {Keywords: Tree embeddings, Range queries, Centroid decomposition, Heavypath decomposition, Diameter, Radius and all Eccentricities computations}
}
Keywords: 

Tree embeddings, Range queries, Centroid decomposition, Heavypath 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 