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
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
