Document Open Access Logo

Algorithms for Length Spectra of Combinatorial Tori

Authors Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, Ivan Yakovlev

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.26.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Vincent Delecroix
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France
Matthijs Ebbens
  • Institut Fourier, CNRS, Université Grenoble Alpes, France
Francis Lazarus
  • G-SCOP/Institut Fourier, CNRS, Université Grenoble Alpes, France
Ivan Yakovlev
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France

Funding

  • Lazarus, Francis: This work is supported by the project TOFU of the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d’avenir.

Acknowledgements

We would like to thank Marcos Cossarini who suggested to look at the norm point of view and Bruno Grenet who enlightened us about the Polynomial Identity Testing problem. We would also like to thank the referees for their helpful comments, in particular for suggesting the complexity improvement in the case of unweighted graphs.

Cite As Get BibTex

Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev. Algorithms for Length Spectra of Combinatorial Tori. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.26

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Geometric topology
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Enumeration
Keywords
  • graphs on surfaces
  • length spectrum
  • polyhedral norm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Peter Buser. Geometry and Spectra of Compact Riemann Surfaces. Birkhäuser, 1992. Google Scholar
  2. Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-source shortest paths in embedded graphs. SIAM Journal on Computing, 42(4):1542-1571, 2013. Google Scholar
  3. Sergio Cabello, Éric Colin de Verdière, and Francis Lazarus. Algorithms for the edge-width of an embedded graph. Computational Geometry, 45(5-6):215-224, 2012. Google Scholar
  4. Sergio Cabello and Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete & Computational Geometry, 37(2):213-235, 2007. Google Scholar
  5. Marcos Cossarini. Discrete surfaces with length and area and minimal fillings of the circle. PhD thesis, Instituto de Matemática Pura e Aplicada (IMPA), 2018. Google Scholar
  6. Éric Colin de Verdière and Jeff Erickson. Tightening nonsimple paths and cycles on surfaces. SIAM Journal on Computing, 39(8):3784-3813, 2010. Google Scholar
  7. Matthijs Ebbens and Francis Lazarus. Computing the length spectrum of combinatorial graphs on the torus. 38th International Symposium on Computational Geometry: Young Researchers Forum, 2022. Google Scholar
  8. David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 599-608, 2003. Google Scholar
  9. Jeff Erickson. Combinatorial optimization of cycles and bases. In Afra Zomorodian, editor, Advances in Applied and Computational Topology, Proceedings of Symposia in Applied Mathematics, 2012. Google Scholar
  10. Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry, 31(1):37-59, 2004. Google Scholar
  11. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 313-322, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993679.
  12. Philip N Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 146-155, 2005. Google Scholar
  13. Martin Kutz. Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time. In 22nd Annual ACM Symposium on Computational Geometry, pages 430-437, 2006. Google Scholar
  14. Bojan Mohar and Carsten Thomassen. Graphs on surfaces, volume 10. JHU press, 2001. Google Scholar
  15. Jean-Pierre Otal. Le spectre marqué des longueurs des surfaces à courbure négative. Annals of Mathematics, 131(1):151-162, 1990. Google Scholar
  16. Hugo Parlier. Interrogating surface length spectra and quantifying isospectrality. Mathematische Annalen, 370(3):1759-1787, 2018. URL: https://math.uni.lu/parlier/Papers/Isospectral2016-11-07.pdf.
  17. Mikael de la Salle. On norms taking integer values on the integer lattice. Comptes Rendus Mathématique, 354(6):611-613, 2016. Google Scholar
  18. Abdoul Karim Sane. Intersection norms and one-faced collections. Comptes Rendus Mathématique, 358(8):941-956, 2020. Google Scholar
  19. Alexander Schrijver. On the uniqueness of kernels. Journal of Combinatorial Theory, Series B, 55(1):146-160, 1992. Google Scholar
  20. Alexander Schrijver. Graphs on the torus and geometry of numbers. Journal of Combinatorial Theory, Series B, 58(1):147-158, 1993. Google Scholar
  21. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach., 27:701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  22. John Stillwell. Classical topology and combinatorial group theory, volume 72. Springer Science & Business Media, 1993. Google Scholar
  23. Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. Journal of Combinatorial Theory, Series B, 48(2):155-177, 1990. Google Scholar
  24. William P. Thurston. A norm for the homology of 3-manifolds. In Mem. Amer. Math. Soc., volume 339, pages 99-130. AMS, 1986. Google Scholar
  25. Marie-France Vignéras. Isospectral and non-isometric Riemannian manifolds. Ann. Math. (2), 112:21-32, 1980. URL: https://doi.org/10.2307/1971319.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact