A Separator Theorem for Nonplanar Graphs
From MaRDI portal
Publication:3971676
Recommendations
Cites work
Cited in
(80)- scientific article; zbMATH DE number 19813 (Why is no real title available?)
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Product structure extension of the Alon-Seymour-Thomas theorem
- Complete Minors in Graphs Without Sparse Cuts
- Edge separators for graphs excluding a minor
- Recent progress towards Hadwiger's conjecture
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Product structure of graphs with an excluded minor
- Partitioning \(H\)-minor free graphs into three subgraphs with no large components
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Modularity of minor‐free graphs
- Balanced line separators of unit disk graphs
- Extremal density for sparse minors and subdivisions
- The one-visibility localization game
- Separator theorems and Turán-type results for planar intersection graphs
- Optimality of geometric local search
- Linearity of grid minors in treewidth with applications through bidimensionality
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles
- A separator theorem for string graphs and its applications
- Finding and using expanders in locally sparse graphs
- Packing minor-closed families of graphs into complete graphs
- Testing outerplanarity of bounded degree graphs
- Divisible subdivisions
- Isometric universal graphs
- A Separator Theorem for String Graphs and Its Applications
- Distributed corruption detection in networks
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- A tight analysis of geometric local search
- On the separation profile of infinite graphs
- Disjoint complete minors and bipartite minors
- The Ramsey number of the clique and the hypercube
- A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
- Single source shortest paths in \(H\)-minor free graphs
- Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
- On graph thickness, geometric thickness, and separator theorems
- On the treewidth of random geometric graphs and percolated grids
- Graph separators: A parameterized view
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Every minor-closed property of sparse graphs is testable
- Fast separation in a graph with an excluded minor
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Chasing a fast robber on planar graphs and random graphs
- Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
- Shortest-path queries in static networks
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Separators in region intersection graphs
- Ramsey numbers of cubes versus cliques
- Some recent progress and applications in graph minor theory
- Packing minor closed families of graphs
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Partitioning \(H\)-minor free graphs into three subgraphs with no large components
- Layered separators in minor-closed graph classes with applications
- The separator theorem for rooted directed vertex graphs
- Extremal functions for sparse minors
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Short and simple cycle separators in planar graphs
- Small complete minors above the extremal edge density
- Sharp separation and applications to exact and parameterized algorithms
- Clustered 3-colouring graphs of bounded degree
- The size and depth of layered Boolean circuits
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Faster shortest-path algorithms for planar graphs
- On the Ramsey number of the triangle and the cube
- On the block number of graphs
- Almost exact matchings
- On the Fiedler value of large planar graphs (extended abstract)
- The first order definability of graphs with separators via the Ehrenfeucht game
- Tree-depth, subgraph coloring and homomorphism bounds
- Vulnerability of nearest neighbor graphs
- On the Fiedler value of large planar graphs
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Transversals of longest cycles in partial k‐trees and chordal graphs
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Bidimensionality and kernels
- Orthogonal tree decompositions of graphs
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Packing spanning graphs from separable families
- Bulky subgraphs of the hypercube
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)
