Interval representation of balanced separators in graphs avoiding a minor

Robert Šámal, 1 Nov 2021

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