Output-sensitive algorithm for the edge-width of an embedded graph

DOI10.1145/1810959.1810987MaRDI QIDQ5405877zbMATH OpenOpenAlexFDO

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

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1810959.1810987

zbMATH Keywords

computational topologyedge-widthembedded graphface-widthsurfacetopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

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

Cited in

(5)

• On the Wimer method for designing edge-based algorithms
• Algorithms for the edge-width of an embedded graph
• Global minimum cuts in surface embedded graphs
• Algorithms for length spectra of combinatorial tori
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs

This page was built for publication: Output-sensitive algorithm 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 Q5405877)