Obstructions for the Disk and the Cylinder Embedding Extension Problems
From MaRDI portal
Publication:4314155
DOI10.1017/S0963548300001279zbMath0808.05041MaRDI QIDQ4314155
Publication date: 9 March 1995
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Characterizing 2-crossing-critical graphs ⋮ Obstructions for two-vertex alternating embeddings of graphs in surfaces ⋮ The structure of graphs not topologically containing the Wagner graph ⋮ Embedding of sign-regular signed graphs and its spectral analysis ⋮ Projective plan and Möbius band obstructions ⋮ 2-restricted extensions of partial embeddings of graphs ⋮ Maximum cycle packing using SPR-trees
Cites Work
- A linear algorithm for embedding planar graphs using PQ-trees
- Adjacency in binary matroids
- Disjoint paths in graphs
- 2-linked graphs
- Graph minors. IX: Disjoint crossed paths
- A Kuratowski theorem for nonorientable surfaces
- Time bounded random access machines
- Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- A structural characterization of planar combinatorial graphs
- Classification and detection of obstructions to planarity
- Depth-First Search and Kuratowski Subgraphs
- Embedding Graphs in the Plane—Algorithmic Aspects
- A Polynomial Solution to the Undirected Two Paths Problem
- Efficient Planarity Testing
- Projective Planarity in Linear Time
