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