Algorithms for the edge-width of an embedded graph

DOI10.1016/j.comgeo.2011.12.002zbMath1241.05023OpenAlexW1987965173MaRDI QIDQ419374

Sergio Cabello, Francis Lazarus, Éric Colin de Verdière

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

face-widthembedded graphcomputational topologyedge-widthtopological graph theory

Mathematics Subject Classification ID

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

Related Items (1)

Discrete systolic inequalities and decompositions of triangulated surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Locally planar graphs are 5-choosable
• Graph minors. VII: Disjoint paths on a surface
• Five-coloring maps on surfaces
• Optimally cutting a surface into a disk
• Flexibility of polyhedral embeddings of graphs in surfaces
• Disjoint paths, planarizing cycles, and spanning walks
• On Short Noncontractible Cycles in Embedded Graphs
• The Independence Ratio and Genus of a Graph
• Computing the orientable genus of projective graphs
• Finding shortest non-trivial cycles in directed graphs on surfaces

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