Sublinear separators, fragility and subexponential expansion
type: Item
instance of: scholarly article
title: Sublinear separators, fragility and subexponential expansion
zbMATH Open document ID: 1327.05316
author: Zdeněk Dvořák
published in: European Journal of Combinatorics
publication date: 2015-12-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1404.7219
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6520154
zbMATH Keywords: balanced separators
zbMATH Keywords: graph decompositions
MaRDI profile type: Publication
OpenAlex ID: W2158237076
arXiv ID: 1404.7219
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
cites work: The isoperimetric number of random regular graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Exact algorithms for the Hamiltonian cycle problem in planar graphs
cites work: Contraction decomposition in h-minor-free graphs and algorithmic applications
cites work: Excluding any graph as a minor allows a low tree-width 2-coloring
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Kernelization and Sparseness: the case of Dominating Set
cites work: On forbidden subdivision characterizations of graph classes
cites work: Testing first-order properties for subclasses of sparse graphs
cites work: Small graph classes and bounded expansion
cites work: Diameter and treewidth in minor-closed graph families
cites work: Separator based sparsification. I: Planarity testing and minimum spanning trees
cites work: Separator-Based Sparsification II: Edge and Vertex Connectivity
cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
cites work: Q4198056
cites work: A separator theorem for graphs of bounded genus
cites work: Planar separators and parallel polygon triangulation.
cites work: Compact topological minors in graphs
cites work: Shortest paths in directed planar graphs with negative lengths
cites work: Topological cliques in graphs II
cites work: Small topological complete subgraphs of ``dense'' graphs
cites work: A Separator Theorem for Planar Graphs
cites work: Applications of a Planar Separator Theorem
cites work: Grad and classes with bounded expansion. I: Decompositions
cites work: Grad and classes with bounded expansion. II: Algorithmic aspects
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Characterisations and examples of graph classes with bounded expansion
cites work: Q3688439
cites work: Q3128907
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: An extremal function for contractions of graphs
DOI: 10.1016/J.EJC.2015.09.001
description: scientific article