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.SoCG.2023.26
URN: urn:nbn:de:0030-drops-178765
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17876/
Delecroix, Vincent ;
Ebbens, Matthijs ;
Lazarus, Francis ;
Yakovlev, Ivan
Algorithms for Length Spectra of Combinatorial Tori
Abstract
Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just listing the length values of the marked length spectrum in increasing order.
In this paper, we describe algorithms for computing the (un)marked length spectra of graphs embedded on the torus. More specifically, we preprocess a weighted graph of complexity n in time O(n² log log n) so that, given a cycle with ? edges representing a free homotopy class, the length of a shortest homotopic cycle can be computed in O(?+log n) time. Moreover, given any positive integer k, the first k values of its unmarked length spectrum can be computed in time O(k log n).
Our algorithms are based on a correspondence between weighted graphs on the torus and polyhedral norms. In particular, we give a weight independent bound on the complexity of the unit ball of such norms. As an immediate consequence we can decide if two embedded weighted graphs have the same marked spectrum in polynomial time. We also consider the problem of comparing the unmarked spectra and provide a polynomial time algorithm in the unweighted case and a randomized polynomial time algorithm otherwise.
BibTeX - Entry
@InProceedings{delecroix_et_al:LIPIcs.SoCG.2023.26,
author = {Delecroix, Vincent and Ebbens, Matthijs and Lazarus, Francis and Yakovlev, Ivan},
title = {{Algorithms for Length Spectra of Combinatorial Tori}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {26:1--26:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-273-0},
ISSN = {1868-8969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17876},
URN = {urn:nbn:de:0030-drops-178765},
doi = {10.4230/LIPIcs.SoCG.2023.26},
annote = {Keywords: graphs on surfaces, length spectrum, polyhedral norm}
}
|
Keywords: |
|
graphs on surfaces, length spectrum, polyhedral norm |
|
Collection: |
|
39th International Symposium on Computational Geometry (SoCG 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
09.06.2023 |
