Characterisations and Examples of Graph Classes with Bounded Expansion

Abstract

Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erdös-Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed $d>0$, there exists a class with bounded expansion, such that a random graph of order $n$ and edge probability $d/n$ asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class.

References in corpus (3)

• Clique Minors in Cartesian Products of Graphs
• The complexity of nonrepetitive edge coloring of graphs
• The order of the largest complete minor in a random graph

Cited by in corpus (32)

• An annotated bibliography on 1-planarity
• A Survey on Graph Drawing Beyond Planarity
• Nonrepetitive Colouring via Entropy Compression
• Layered Separators in Minor-Closed Graph Classes with Applications
• Defective colouring of graphs excluding a subgraph or minor
• Improved bounds for centered colorings
• Planar graphs have bounded nonrepetitive chromatic number
• A unified approach to structural limits, and limits of graphs with bounded tree-depth
• Extremal density for sparse minors and subdivisions
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• Stack-number is not bounded by queue-number
• Graph sharing games: complexity and connectivity
• Notes on Graph Product Structure Theory
• Sparsity and dimension
• Separating layered treewidth and row treewidth
• Homomorphism counts in robustly sparse graphs
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Testing first-order properties for subclasses of sparse graphs
• Induced subdivisions with pinned branch vertices
• Nonrepetitive graph colouring
• The Thue choice number versus the Thue chromatic number of graphs
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• Sublinear separators, fragility and subexponential expansion
• Anagram-free colourings of graph subdivisions
• Rainbow independent sets on dense graph classes
• On the largest reduced neighborhood clique cover number of a graph
• List rankings and on-line list rankings of graphs
• The $k$-strong induced arboricity of a graph
• Largest reduced neighborhood clique cover number revisited
• Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
• Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application