A Separator Theorem for Nonplanar Graphs
From MaRDI portal
Publication:3971676
DOI10.2307/1990903zbMath0747.05051OpenAlexW4241860363WikidataQ56235105 ScholiaQ56235105MaRDI QIDQ3971676
Robin Thomas, Noga Alon, P. D. Seymour
Publication date: 25 June 1992
Full work available at URL: https://doi.org/10.2307/1990903
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)
Related Items (72)
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Packing minor-closed families of graphs into complete graphs ⋮ Graph separators: A parameterized view ⋮ Clustered 3-colouring graphs of bounded degree ⋮ A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings ⋮ Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Disjoint complete minors and bipartite minors ⋮ Packing spanning graphs from separable families ⋮ Small complete minors above the extremal edge density ⋮ A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes ⋮ Packing minor closed families of graphs ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time ⋮ Layered separators in minor-closed graph classes with applications ⋮ Some recent progress and applications in graph minor theory ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ On the separation profile of infinite graphs ⋮ Transversals of longest cycles in partial k‐trees and chordal graphs ⋮ Divisible subdivisions ⋮ The one-visibility localization game ⋮ Graph coloring with no large monochromatic components ⋮ On graph thickness, geometric thickness, and separator theorems ⋮ Modularity of minor‐free graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ The size and depth of layered Boolean circuits ⋮ Almost exact matchings ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Edge separators for graphs excluding a minor ⋮ Recent progress towards Hadwiger's conjecture ⋮ Finding and Using Expanders in Locally Sparse Graphs ⋮ Unnamed Item ⋮ On the Fiedler value of large planar graphs ⋮ On the Block Number of Graphs ⋮ Vulnerability of nearest neighbor graphs ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Testing outerplanarity of bounded degree graphs ⋮ Separator theorems and Turán-type results for planar intersection graphs ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Ramsey numbers of cubes versus cliques ⋮ On the Ramsey number of the triangle and the cube ⋮ Every minor-closed property of sparse graphs is testable ⋮ Shortest-path queries in static networks ⋮ Unnamed Item ⋮ Faster shortest-path algorithms for planar graphs ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Tree-depth, subgraph coloring and homomorphism bounds ⋮ Single source shortest paths in \(H\)-minor free graphs ⋮ A Separator Theorem for String Graphs and its Applications ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ Optimization and Recognition for K 5-minor Free Graphs in Linear Time ⋮ Balanced line separators of unit disk graphs ⋮ Unnamed Item ⋮ Distributed Corruption Detection in Networks ⋮ Bidimensionality and Kernels ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ On the treewidth of random geometric graphs and percolated grids ⋮ Bulky subgraphs of the hypercube ⋮ Separators in region intersection graphs ⋮ The Ramsey number of the clique and the hypercube ⋮ Isometric Universal Graphs ⋮ Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ Unnamed Item ⋮ Short and Simple Cycle Separators in Planar Graphs ⋮ Extremal functions for sparse minors ⋮ A tight analysis of geometric local search
Cites Work
This page was built for publication: A Separator Theorem for Nonplanar Graphs
