Algorithms for the edge-width of an embedded graph
From MaRDI portal
Publication:419374
DOI10.1016/J.COMGEO.2011.12.002zbMATH Open1241.05023OpenAlexW1987965173MaRDI QIDQ419374FDOQ419374
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
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
Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Graphs on surfaces
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Embeddings of graphs with no short noncontractible cycles
- Five-coloring maps on surfaces
- Title not available (Why is that?)
- Disjoint paths, planarizing cycles, and spanning walks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Flexibility of polyhedral embeddings of graphs in surfaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. VII: Disjoint paths on a surface
- Optimally cutting a surface into a disk
- Greedy optimal homotopy and homology generators
- Finding one tight cycle
- Multiple source shortest paths in a genus \(g\) graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Short Noncontractible Cycles in Embedded Graphs
- The Independence Ratio and Genus of a Graph
- Title not available (Why is that?)
- Computing the orientable genus of projective graphs
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Locally planar graphs are 5-choosable
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)
