Finding shortest non-separating and non-contractible cycles for topologically embedded graphs

DOI10.1007/s00454-006-1292-5zbMath1115.05019OpenAlexW1522210445MaRDI QIDQ878074

Bojan Mohar, Sergio Cabello

Publication date: 26 April 2007

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-006-1292-5

zbMATH Keywords

algorithmsurfacegenusface-width

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (17)

Minimum Cuts in Surface Graphs ⋮ Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ Untangling two systems of noncrossing curves ⋮ Computing the shortest essential cycle ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Algorithms for the edge-width of an embedded graph ⋮ Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations ⋮ Homomorphisms between graphs embedded in surfaces ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Approximating the Crossing Number of Toroidal Graphs ⋮ Unnamed Item ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Dynamic programming for graphs on surfaces ⋮ Unnamed Item ⋮ Discrete systolic inequalities and decompositions of triangulated surfaces

This page was built for publication: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs