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

graphalgorithmcycleseparatingtopological graph theorycontractiblecellular embedding

Mathematics Subject Classification ID

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

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

(8)

• Topologically trivial closed walks in directed surface graphs
• Survey on path and cycle embedding in some networks
• Hamiltonian cycles in polyhedral maps
• scientific article; zbMATH DE number 7559234 (Why is no real title available?)
• The computational complexity of the solid torus core recognition problem
• Algorithms – ESA 2005
• Some triangulated surfaces without balanced splitting
• 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)