On classes of graphs with strongly sublinear separators. (June 2018)

• Record Type: Journal Article
• Authors: Dvořák, Zdeněk
• Is Part Of: European journal of combinatorics. Volume 71(2018)
• Page Start: 1
• Page End: 11
• Publication Date: 2018-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.02.032
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For real numbers c, ε > 0, let G c, ε 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 ⊆ G c, ε for some c, ε > 0 . We investigate properties of such graph classes, leading in particular to an approximate algorithm to determine membership in G c, ε : there exist c ′ > 0 such that for each input graph G, this algorithm in polynomial time determines either that G ∈ G c ′, ε 2 ∕ 160, or that G ∉ G c, ε .