Finding cycles with topological properties in embedded graphs

DOI10.1137/100810794MaRDI QIDQ3225142zbMATH OpenOpenAlexFDO

Authors S. Cabello, Éric Colin de Verdière, Francis Lazarus

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100810794

zbMATH Keywords

algorithmcellular embeddingcontractiblecyclegraphseparatingtopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Algorithms – ESA 2005
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• The cycle's structure of embedded graphs in surfaces

Cited in

(9)

• Survey on path and cycle embedding in some networks
• Hamiltonian cycles in polyhedral maps
• Topologically trivial closed walks in directed surface graphs
• Some triangulated surfaces without balanced splitting
• Topologically trivial closed walks in directed surface graphs
• Algorithms – ESA 2005
• The computational complexity of the solid torus core recognition problem
• Computation of toroidal Schnyder woods made simple and fast: from theory to practice
• Finding short cycles in embedded graph in polynomial time

This page was built for publication: Finding cycles with topological properties in embedded graphs

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