Obstructions for the Disk and the Cylinder Embedding Extension Problems

DOI10.1017/S0963548300001279MaRDI QIDQ4314155zbMATH OpenFDO

Authors Bojan Mohar

Publication date 9 March 1995

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548300001279

zbMATH Keywords

boundarycylinderdiskembeddingembedding extensionlinear time algorithmsminimal obstructions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Obstructions for simple embeddings
• 2-restricted extensions of partial embeddings of graphs
• Projective plan and Möbius band obstructions
• Obstructions For 2-Möbius Band Embedding Extension Problem
• Universal obstructions for embedding extension problems

Cites work

• 2-linked graphs
• A Kuratowski theorem for nonorientable surfaces
• A linear algorithm for embedding planar graphs using PQ-trees
• A Polynomial Solution to the Undirected Two Paths Problem
• A structural characterization of planar combinatorial graphs
• Adjacency in binary matroids
• Classification and detection of obstructions to planarity
• Depth-First Search and Kuratowski Subgraphs
• Disjoint paths in graphs
• Efficient Planarity Testing
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Embedding Graphs in the Plane—Algorithmic Aspects
• Graph minors. IX: Disjoint crossed paths
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Projective Planarity in Linear Time
• Time bounded random access machines

Cited in

(11)

• Projective plan and Möbius band obstructions
• 2-restricted extensions of partial embeddings of graphs
• Characterizing 2-crossing-critical graphs
• Obstructions For 2-Möbius Band Embedding Extension Problem
• Obstructions for two-vertex alternating embeddings of graphs in surfaces
• The structure of graphs not topologically containing the Wagner graph
• Universal obstructions for embedding extension problems
• Maximum cycle packing using SPR-trees
• Embedding of sign-regular signed graphs and its spectral analysis
• Obstructions for simple embeddings
• scientific article; zbMATH DE number 7746010 (Why is no real title available?)

This page was built for publication: Obstructions for the Disk and the Cylinder Embedding Extension Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4314155)