Rambling on Graphs

# Shortcutting Trees

Over the past two years or so, I have been thinking about a cute problem, which turned out to be much more useful to my research than I initially thought. Here it is:

Tree Shortcutting Problem: Given an edge-weighted tree $T$, add (weighted) edges to $T$, called shortcuts, to get a graph $K$ such that:

1. $d_K(u,v) = d_T(u,v)~\quad \forall u,v\in V(T)$. That is, $K$ preserves distances in $T$.
2. For every $u,v\in V(T)$, there exists a shortest path from $u$ to $v$ in $K$ containing at most $k$ edges for some $k\geq 2$.

The goal is to minimize the product $k \cdot \mathrm{tw}(K)$, where $\mathrm{tw}(K)$ is the treewidth of $K$.

Planar graphs are sparse: any planar graph with $n$ vertices has at most $3n-6$ edges. A simple corollary of this sparsity is that planar graphs are $6$-colorable. There is simple and beautiful proof based on the Euler formula, which can easily be exteded to bounded genus graphs, a more general case: any graph embedddable in orientable surfaces of genus $g$ with $n$ vertices has at most $3n + 6g-6$ edges.
How’s about the number of edges of $K_r$-minor-free graphs? This is a very challenging question. A reasonable speculation is $O(r)\cdot n$: a disjoint union of $n/(r-1)$ copies of $K_{r-1}$ excludes a $K_r$ minor and has $\Theta(r)\cdot n$ edges. But this isn’t the case. And surprisingly, the correct bound is $O(r\sqrt{\log r})n$, which will be the topic of this post.
Theorem 1: Any $K_r$-minor-free graphs with $n$ vertices has at most $O(r\sqrt{\log r})\cdot n$ edges.