Algorithms for the edge-width of an embedded graph

DOI10.1016/J.COMGEO.2011.12.002MaRDI QIDQ419374zbMATH OpenOpenAlexFDO

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

Publication date 18 May 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.418.1572

zbMATH Keywords

computational topologyembedded graphface-widthedge-widthtopological graph theory

Mathematics Subject Classification ID

Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Output-sensitive algorithm for the edge-width of an embedded graph
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Algorithms – ESA 2005
• Shortest non-trivial cycles in directed surface graphs
• Shortest non-trivial cycles in directed and undirected surface graphs

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• scientific article; zbMATH DE number 5506235 (Why is no real title available?)
• scientific article; zbMATH DE number 3709228 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 3562105 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• scientific article; zbMATH DE number 7051285 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• Computing the orientable genus of projective graphs
• Disjoint paths, planarizing cycles, and spanning walks
• Embeddings of graphs with no short noncontractible cycles
• Finding one tight cycle
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Five-coloring maps on surfaces
• Flexibility of polyhedral embeddings of graphs in surfaces
• Graph minors. VII: Disjoint paths on a surface
• Graphs on surfaces
• Greedy optimal homotopy and homology generators
• Locally planar graphs are 5-choosable
• Multiple source shortest paths in a genus \(g\) graph
• On Short Noncontractible Cycles in Embedded Graphs
• Optimally cutting a surface into a disk
• The Independence Ratio and Genus of a Graph

Cited in

(12)

• Embeddings of graphs with no short noncontractible cycles
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Output-sensitive algorithm for the edge-width of an embedded graph
• On the Wimer method for designing edge-based algorithms
• Algorithms for length spectra of combinatorial tori
• Computing the stretch of an embedded graph
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Face-width of embedded graphs
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Algorithms for graphs embeddable with few crossings per edge
• Shortest non-trivial cycles in directed and undirected surface graphs
• Fundamentals of Computation Theory

This page was built for publication: Algorithms for the edge-width of an embedded graph

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