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

DOI10.1007/S00454-006-1292-5zbMATH Open1115.05019OpenAlexW1522210445MaRDI QIDQ878074FDOQ878074

Authors S. Cabello, Bojan Mohar 

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

surfacealgorithmgenusface-width

Mathematics Subject Classification ID

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

Recommendations

• Algorithms – ESA 2005
• Algorithms for the edge-width of an embedded graph
• Shortest non-trivial cycles in directed surface graphs
• Output-sensitive algorithm for the edge-width of an embedded graph
• Finding shortest non-trivial cycles in directed graphs on surfaces

Cited in

(31)

• Shortest non-trivial cycles in directed surface graphs
• Short Topological Decompositions of Non-Orientable Surfaces
• Short topological decompositions of non-orientable surfaces
• Counting and sampling minimum cuts in genus \(g\) graphs
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Space complexity of perfect matching in bounded genus bipartite graphs
• Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations
• Approximating the Crossing Number of Toroidal Graphs
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Finding cycles with topological properties in embedded graphs
• Approximation algorithms for Euler genus and related problems
• Algorithms for the edge-width of an embedded graph
• Ford-Fulkerson algorithm and short cycles in embedded graphs
• Homomorphisms between graphs embedded in surfaces
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• scientific article; zbMATH DE number 7559234 (Why is no real title available?)
• On Short Noncontractible Cycles in Embedded Graphs
• Computing the shortest essential cycle
• Algorithms – ESA 2005
• Topologically trivial closed walks in directed surface graphs
• scientific article; zbMATH DE number 475598 (Why is no real title available?)
• Multiple source shortest paths in a genus \(g\) graph
• Compressed Decision Problems in Hyperbolic Groups.
• Global minimum cuts in surface embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Output-sensitive algorithm for the edge-width of an embedded graph
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Finding short cycles in embedded graph in polynomial time
• Minimum Cuts in Surface Graphs
• Dynamic programming for graphs on surfaces
• Finding shortest non-trivial cycles in directed graphs on surfaces

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q878074)