Document Open Access Logo

Minimum Cycle and Homology Bases of Surface Embedded Graphs

Authors Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, Amir Nayyeri

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.23.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Cycle basis
  • Homology basis
  • Topological graph theory

Metrics

Abstract

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis.

For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

Cite As Get BibTex

Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum Cycle and Homology Bases of Surface Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.23

Author Details

Glencora Borradaile
Erin Wolf Chambers
Kyle Fox
Amir Nayyeri

References

  1. L. Aleksandrov and H. Djidjev. Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. of Disc. Math., 9(1):129-150, 1996. Google Scholar
  2. Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, and Romeo Rizzi. Breaking the O(m² n) barrier for minimum cycle bases. In Proc. 17th Ann. Euro. Symp. Algo., pages 301-312, 2009. Google Scholar
  3. Franziska Berger, Peter Gritzmann, and Sven de Vries. Minimum cycle bases for network graphs. Algorithmica, 40(1):51-62, 2004. Google Scholar
  4. G. Borradaile, P. Sankowski, and C. Wulff-Nilsen. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Trans. Algo., 11(3):16, 2015. Google Scholar
  5. Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Proc. 32nd Ann. Int. Symp. Comput. Geom., 2016. Google Scholar
  6. Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang. Annotating simplicies with a homology basis and its applications. In Proc. 13th Scandinavian Workshop on Algo. Theory, pages 189-200, 2012. Google Scholar
  7. Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-source shortest paths in embedded graphs. SIAM J. Comput., 42(4):1542-1571, 2013. Google Scholar
  8. A. C. Cassell, J. C. de Henderson, and K. Ramachandran. Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proc. R. Soc. Lond. Ser. A, 350:61-70, 1976. Google Scholar
  9. L. O. Chua and Li-Kuan Chen. On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans. Circuit Theory, 20:495-503, 1973. Google Scholar
  10. José Coelho de Pina. Applications of Shortest Path Methods. PhD thesis, University of Amsterdam, 1995. Google Scholar
  11. Tamal K. Dey, Jian Sun, and Yusu Wang. Approximating loops in a shortest homology basis from point data. In Proc. 26th Ann. Symp. Comput. Geom., pages 166-175, 2010. Google Scholar
  12. David Eppstein. Dynamic generators of topologically embedded graphs. In Proc. 14th Ann. ACM-SIAM Symp. Disc. Algo., pages 599-608, 2003. Google Scholar
  13. Jeff Erickson. Shortest non-trivial cycles in directed surface graphs. In Proc. 27th Ann. Symp. Comput. Geom., pages 236-243, 2011. Google Scholar
  14. Jeff Erickson and Amir Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In Proc. 22nd Ann. ACM-SIAM Symp. Disc. Algo., pages 1166-1176, 2011. Google Scholar
  15. Jeff Erickson and Kim Whittlesey. Greedy optimal homotopy and homology generators. In Proc. 16th Ann. ACM-SIAM Symp. on Disc. Algo., pages 1038-1046, 2005. Google Scholar
  16. Kyle Fox. Shortest non-trivial cycles in directed and undirected surface graphs. In Proc. 24th Ann. ACM-SIAM Symp. Disc. Algo., pages 352-364, 2013. Google Scholar
  17. Alexander Golynski and Joseph D. Horton. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In Proc. 8th Scandinavian Workshop on Algo. Theory, pages 200-209, 2002. Google Scholar
  18. R. E. Gomory and T. C. Hu. Multi-terminal network flows. J. SIAM, 9(4):551-570, 1961. Google Scholar
  19. Jonathan L. Gross and Thomas W. Tucker. Topological graph theory. Dover Publications, 2001. Google Scholar
  20. D. Hartvigsen and R. Mardon. The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. SIAM J. Disc. Math., 7(3):403-418, 1994. Google Scholar
  21. J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput., 16(2):358-366, 1987. Google Scholar
  22. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proc. 43rd Ann. ACM Symp. Theory Comput., pages 313-322, 2011. Google Scholar
  23. Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E. Paluch. An Õ(m²n) algorithm for minimum cycle basis of graphs. Algorithmica, 52(3):333-349, 2008. Google Scholar
  24. G. Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Poggendorf Ann. Physik, 72:497-508, 1847. English transl. in Trans. Inst. Radio Engrs. CT-5 (1958), pp. 4-7. Google Scholar
  25. Philip Klein. Multiple-source shortest paths in planar graphs. In Proc. 16th Ann. ACM-SIAM Symp. Disc. Algo., pages 146-155, 2005. Google Scholar
  26. Donald E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, 1968. Google Scholar
  27. K. Mehlhorn and D. Michail. Minimum cycle bases: Faster and simpler. ACM Trans. Algo., 6(1):8, 2009. Google Scholar
  28. S. Tazari and M. Müller-Hannemann. Shortest paths in linear time on minor-closed graph classes with an application to Steiner tree approximation. Disc. Applied Math., 157(4):673-684, 2009. Google Scholar
  29. Geetika Tewari, Craig Gotsman, and Steven J. Gortler. Meshing genus-1 point clouds using discrete one-forms. Comput. Graph., 30(6):917-926, 2006. Google Scholar
  30. C. Wulff-Nilsen. Minimum cycle basis and all-pairs min cut of a planar graph in subquadratic time. Technical Report arXiv:0912.1208, University of Copenhagen, 2009. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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