Disjoint homotopic paths and trees in a planar graph

DOI10.1007/BF02574704zbMath0755.05033MaRDI QIDQ1179127

Alexander Schrijver

Publication date: 26 June 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131173

zbMATH Keywords

polynomial-time algorithmdisjoint trees problemhomotopic treesplanar graph embedded

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

The complexity of induced minors and related problems ⋮ Recognizing binet matrices ⋮ Neighborhood persistency of the linear optimization relaxation of integer linear optimization ⋮ Obstruction sets for outer-cylindrical graphs ⋮ On obstructions to small face covers in planar graphs ⋮ DRAWING WITH FAT EDGES ⋮ Pure Nash equilibria in graphical games and treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Disjoint circuits of prescribed homotopies in a graph on a compact surface
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XV: Giant steps

This page was built for publication: Disjoint homotopic paths and trees in a planar graph