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).

2more comments