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

read more

Sparsity of minor-free graphs

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.

read more