# On classes of graphs with strongly sublinear separators

@inproceedings{Dvovrak2017OnCO, title={On classes of graphs with strongly sublinear separators}, author={Zdenvek Dvovr'ak}, year={2017} }

For real numbers c, ε > 0, let Gc,ε denote the class of graphs G such that each subgraph H of G has a balanced separator of order at most c|V (H)|1−ε. A class G of graphs has strongly sublinear separators if G ⊆ Gc,ε for some c, ε > 0. We investigate properties of such graph classes, leading in particular to an approximate algorithm to determine membership in Gc,ε: there exist c > 0 such that for each input graphG, this algorithm in polynomial time determines either that G ∈ Gc′,ε2/160, or that… Expand

#### Topics from this paper

#### References

SHOWING 1-10 OF 18 REFERENCES

Finding small balanced separators

- Mathematics, Computer Science
- STOC '06
- 2006

This paper gives a randomized algorithm that finds an α-separator of size k in the given graph, unless the graph contains an (α+ε)-separators of size strictly less than k, in which case the algorithm finds one such separator. Expand

A Separator Theorem for Graphs of Bounded Genus

- Mathematics, Computer Science
- J. Algorithms
- 1984

The main result of this paper is that if the authors can draw a graph on a surface of genus g, then they can bisect it by removing $O(\sqrt{gn})$ vertices, best possible to within a constant factor. Expand

A separator theorem for graphs with an excluded minor and its applications

- Mathematics, Computer Science
- STOC '90
- 1990

It follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/ √ log n in polynomial time, find that size exactly and solve any sparse system of n linear equations in n unknowns in time O(n). Expand

Reduced constants for simple cycle graph separation

- Computer Science, Mathematics
- Acta Informatica
- 1997

If G is an n vertex maximal planar graph and δ≤1 3, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B has weight exceeding 1−δ, and C is a simple cycle with no more than 2√n+O(1) vertices. Expand

Polynomial expansion and sublinear separators

- Mathematics, Computer Science
- Eur. J. Comb.
- 2018

It is proved that if for some fixed 0 δ ≤ 1, every n -vertex graph of C has a balanced separator of order O ( n 1 − δ ) , then any depth- r minor obtained by contracting disjoint subgraphs of radius at most r of a graph in C has average degree O ( r polylog r ) 1 ∕ δ . Expand

Improved approximation algorithms for minimum-weight vertex separators

- Mathematics, Computer Science
- STOC '05
- 2005

The algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces is developed, and an O(√log n) pseudo-approximation for finding balanced vertices in general graphs is exhibited. Expand

Graph Minors

- 2009

For a given graph G and integers b, f ≥ 0, let S be a subset of vertices of G of size b + 1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by… Expand

Shallow excluded minors and improved graph decompositions

- Mathematics, Computer Science
- SODA '94
- 1994

The notion of the limited-depth minor exclusion is introduced and it is proved that graphs that exclude small limited- depth minors have relatively small separators, which implies that any graph that excludes Kh as a minor has an O(hpn logn)-sized separator. Expand

A Separator Theorem in Minor-Closed Classes

- Mathematics, Computer Science
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- 2010

It is shown that for each t, there is a separator of size O(t \sqrt{n}) in any $n$-vertex graph G with no $K_t$-minor in any time, and an algorithm aspects of the separator theorem are discussed. Expand

A Separator Theorem for Planar Graphs

- Mathematics
- 1977

Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more… Expand