Interval representation of balanced separators in graphs avoiding a minor

We show that for any sufficiently large graph \(G\) avoiding \(K_k\) as a minor, we can map vertices \(v \in V (G)\) to intervals \(I(v) ⊆ [0, 1]\) so that

1. \(I(u) \cap I(v) \neq \emptyset\) for each edge \(uv\),
2. the sum of the squares of the lengths of these intervals is \(\mathcal{O}(k^6 \log k)\), and
3. the average distance between the intervals is at least \(\frac{1}{25}\)

Balanced separators of \(G\) of sublinear size (with various additional properties) can be read off this representation.

This is joint work with Zdeněk Dvořák and Jakub Pekárek

Recording