Graph minors. XI: Circuits on a surface

DOI10.1006/JCTB.1994.1007MaRDI QIDQ1322009zbMATH OpenOpenAlexFDO

Authors Neil Robertson, Paul Seymour

Publication date 14 November 1994

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1994.1007

zbMATH Keywords

graph minorsurfacetangle

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65)

Review text

This paper provides preliminary work to be applied towards proving a theorem on graphs with the exclusion of a fixed minor. One component of this proof involves graphs drawn on a surface. The lemmas of the current paper enable the authors to treat the case where the surface is a sphere in the same manner as the case of higher genus. The main tool is the tangle, defined in earlier papers by the authors.

Recommendations

• Graph minors. XII: Distance on a surface
• Graph minors. XV: Giant steps
• Graph minors. XVI: Excluding a non-planar graph

Cited in

(28)

• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Grids and their minors
• Circuits in graphs embedded on the torus
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Graph minors. XIX: Well-quasi-ordering on a surface.
• Graph minors. XVII: Taming a vortex
• Excluding subdivisions of bounded degree graphs
• Graph minors. XII: Distance on a surface
• Graph minors. XV: Giant steps
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Approximation algorithms via contraction decomposition
• The theory of guaranteed search on graphs
• The branchwidth of graphs and their cycle matroids
• Fixed-parameter tractability of treewidth and pathwidth
• The Induced Disjoint Paths Problem
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Subexponential parameterized algorithms
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
• Packing topological minors half‐integrally
• A survey of parameterized algorithms and the complexity of edge modification
• Algorithms for finding an induced cycle in planar graphs
• Excluding sums of Kuratowski graphs
• Excluding disjoint Kuratowski graphs
• Rank-width and tree-width of \(H\)-minor-free graphs
• A structural approach to tree decompositions of knots and spatial graphs
• Some recent progress and applications in graph minor theory

This page was built for publication: Graph minors. XI: Circuits on a surface

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