On classes of graphs with strongly sublinear separators

DOI10.1016/J.EJC.2018.02.032MaRDI QIDQ1750205zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák

Publication date 18 May 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.03117

zbMATH Keywords

approximate algorithmbalanced separator

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Abstract: For real numbers c,epsilon>0, let G_{c,epsilon} 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-epsilon}. A class of graphs has strongly sublinear separators if it is a subclass of G_{c,epsilon} for some c,epsilon>0. We investigate properties of such graph classes, leading in particular to an approximate algorithm to determine membership in G_{c,epsilon}: there exist c'>0 such that for each input graph G, this algorithm in polynomial time determines either that G belongs to G_{c',epsilon^2/160}, or that G does not belong to G_{c,epsilon}.

Recommendations

• Strongly sublinear separators and polynomial expansion
• Sublinear separators, fragility and subexponential expansion
• A note on sublinear separators and expansion
• Approximating small balanced vertex separators in almost linear time
• Approximating small balanced vertex separators in almost linear time

Cites work

• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Finding small balanced separators
• First order properties on nowhere dense structures
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Reduced constants for simple cycle graph separation
• Sparsity. Graphs, structures, and algorithms
• Strongly sublinear separators and polynomial expansion
• Sublinear separators, fragility and subexponential expansion

Cited in

(10)

• Polynomial expansion and sublinear separators
• Notes on graph product structure theory
• A note on sublinear separators and expansion
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• Strongly sublinear separators and polynomial expansion
• Sublinear separators in intersection graphs of convex shapes
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• On weighted sublinear separators
• Small balanced vertex separators in NFA to regular expression conversion
• Sublinear separators, fragility and subexponential expansion

This page was built for publication: On classes of graphs with strongly sublinear separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1750205)