Finding cycles with topological properties in embedded graphs

DOI10.1137/100810794zbMATH Open1237.05112OpenAlexW2082719291MaRDI QIDQ3225142FDOQ3225142

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

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

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)

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
• Title not available (Why is that?)
• 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)