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

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

zbMATH Keywords

surfacealgorithmgenusface-width

Mathematics Subject Classification ID

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

Cited In (31)

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