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

DOI10.1145/1810959.1810987zbMATH Open1284.05179OpenAlexW2133225996MaRDI QIDQ5405877FDOQ5405877

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

surfacecomputational topologyembedded graphface-widthedge-widthtopological graph theory

Mathematics Subject Classification ID

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

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)

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

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)