# Graph properties that imply a bounded number of edges

Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a property that is known to imply a bound on number of edges (as probably most people do). For example, whether the graph is planar.

My question is what graph properties imply a bounded number of edges. I assume that there are such properties that I am not familiar with, and it seems quite useful to have a list of these properties. I am only interested in cases where the number of edges is asymptotically smaller than $n^2$ (for example, Turan's Theorem is not relevant).

Some properties that I am already familiar with:

• Planar graphs have $O(n)$ edges. There are several variants, such as quasi-planar graphs, with linear or almost linear bounds.
• The Zarankiewicz problem states that a graph that contains no copy of $K_{s,t}$ has $O(n^{2-1/s})$ edges (this is the formulation for the case where $s$ and $t$ are constants).
• Moore's bound states that a graph of girth larger than $2k$ contains $O(n^{1+1/k})$ edges.
• Families of graphs that are closed under taking induced subgraphs and have sufficiently small separators have $O(n)$ edges (e.g., see Fox and Pach).
• Any minor-closed class of graphs that excludes at least one complete graph has only a linear number of edges. – Gordon Royle Jun 15 '17 at 0:31
• Graphs with $n$ vertices and excluding $K_t$ as a topological minor (i.e. as a subdivision) have $O(t^2 n)$ edges. – David Wood Jun 15 '17 at 9:13
• Graphs with $n$ vertices that can be drawn on a fixed surface with $O(n)$ crossings have $O(n)$ edges. This follows from the crossing lemma. More generally, graphs with $n$ vertices that can be drawn on a fixed surface with $O(n^{4-3\epsilon})$ crossings have $O(n^{2-\epsilon})$ edges. – David Wood Jun 15 '17 at 9:27
• In the comment about the Zarankiewicz problem, should $O(n^{1-1/s})$ be $O(n^{2-1/s})$? – David Wood Jun 15 '17 at 9:42
• The Zarankiewicz problem generalises to any bipartite Turan problem (i.e. forbidding any fixed bipartite graph as a subgraph). The bound for graphs of girth larger than $2k$ fits into this framework as Bondy and Simonovits proved that any graph without a cycle of length $2k$ has at most $20kn^{1+1/k}$ edges. – Jon Noel Jun 16 '17 at 6:48

$n$-vertex graphs in a hereditary class $X$ have $o(n^2)$ vertices if and only if graphs in $X$ are ($K_p$, $K_{t,t}$)-free for some constants $p$ and $t$ (i.e., do not contain $K_p$ and $K_{t,t}$ as induced subgraphs). This is equivalent to saying that graphs in $X$ do not contain $K_{q,q}$ as a subgraph for some constant $q$.
1. Planar graphs are $(K_5, K_{3,3})$-free;
2. Graphs of girth larger than 4 are $(K_3, K_{2,2})$-free.