Graph minors. VII: Disjoint paths on a surface
From MaRDI portal
Publication:1111568
DOI10.1016/0095-8956(88)90070-6zbMath0658.05044OpenAlexW2003311624MaRDI QIDQ1111568
Publication date: 1988
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(88)90070-6
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)
Related Items
Graph minors. VI. Disjoint paths across a disc, Graph minors. V. Excluding a planar graph, Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces, A theorem on paths in locally planar triangulations, Unnamed Item, Book embedding of locally planar graphs on orientable surfaces, Rooted routing in the plane, Unnamed Item, Grids and their minors, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph minors. VIII: A Kuratowski theorem for general surfaces, A simple construction of high representativity triangulations, Planar graphs on the projective plane, The \(\mathbb{Z}_2\)-genus of Kuratowski minors, 2-connected spanning subgraphs with low maximum degree in locally planar graphs, Non-revisiting paths on surfaces with low genus, Some recent progress and applications in graph minor theory, 3-colorable even embeddings on closed surfaces, \(K_{6}\)-minors in triangulations on the nonorientable surface of genus 3, The disjoint shortest paths problem, The Induced Disjoint Paths Problem, Immersion in four-edge-connected graphs, The Erdős-Pósa property for clique minors in highly connected graphs, Graph minors. XXII. Irrelevant vertices in linkage problems, A linear time algorithm for the induced disjoint paths problem in planar graphs, Algorithms for the edge-width of an embedded graph, 5-chromatic even triangulations on surfaces, Unnamed Item, Three-coloring triangle-free graphs on surfaces. VI: 3-colorability of quadrangulations, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Subgraphs of graphs on surfaces with high representativity, The theory of guaranteed search on graphs, Dominating sets in triangulations on surfaces, Graph minors. XIX: Well-quasi-ordering on a surface., Spanning closed walks and TSP in 3-connected planar graphs, Algorithms for finding an induced cycle in planar graphs, Representations of graphs and networks (coding, layouts and embeddings), Disjoint homotopic paths and trees in a planar graph, Odd complete minors in even embeddings on surfaces, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Generating maps on surfaces, Circuits in graphs embedded on the torus, Locally planar graphs are 5-choosable, Regular maps on surfaces with large planar width, On obstructions to small face covers in planar graphs, On the uniqueness of kernels, Unnamed Item, Explicit bounds for graph minors, 2- and 3-factors of graphs on surfaces, Toroidal grid minors and stretch in embedded graphs, Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs, Coloring-flow duality of embedded graphs, Disjoint circuits of prescribed homotopies in a graph on a compact surface, Graph minors. XXI. graphs with unique linkages, A partial k-arboretum of graphs with bounded treewidth, Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, Unnamed Item, On essential and inessential polygons in embedded graphs, Colouring Eulerian triangulations, Coloring locally bipartite graphs on surfaces., Long cycles in graphs on a fixed surface, 5-chromatic even triangulations on the Klein bottle, Unnamed Item, Graph minors. III. Planar tree-width, Disjoint Paths—A Survey, Locally planar graphs are 5-paintable, Discrete systolic inequalities and decompositions of triangulated surfaces, Even Embeddings of the Complete Graphs and Their Cycle Parities
Cites Work
