A Separator Theorem for Nonplanar Graphs
From MaRDI portal
Publication:3971676
DOI10.2307/1990903zbMATH Open0747.05051OpenAlexW4241860363WikidataQ56235105 ScholiaQ56235105MaRDI QIDQ3971676FDOQ3971676
Authors: Noga Alon, Robin Thomas, 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 (81)
- Extremal density for sparse minors and subdivisions
- Title not available (Why is that?)
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Product structure extension of the Alon-Seymour-Thomas theorem
- Modularity of minor‐free graphs
- Partitioning \(H\)-minor free graphs into three subgraphs with no large components
- 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
- 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
- Isometric universal graphs
- 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
- 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
- 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
- Orthogonal tree decompositions of graphs
- 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
- Bulky subgraphs of the hypercube
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- 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
- Finding and using expanders in locally sparse graphs
- Fast separation in a graph with an excluded minor
- Small complete minors above the extremal edge density
- A separator theorem for string graphs and its applications
- Distributed corruption detection in networks
- Almost exact matchings
- Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Some recent progress and applications in graph minor theory
- Optimality of geometric local search
- On graph thickness, geometric thickness, and separator theorems
- 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
- Chasing a fast robber on planar graphs and random 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
- Partitioning \(H\)-minor free graphs into three subgraphs with no large components
- The separator theorem for rooted directed vertex graphs
- Testing outerplanarity of bounded degree graphs
- 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
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Short and simple cycle separators in planar graphs
- Local search is a PTAS for feedback vertex set in minor-free graphs
- On the block number of graphs
- Bidimensionality and kernels
- Disjoint complete minors and bipartite minors
- On the Ramsey number of the triangle and the cube
- 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)
