About me - Hung Le / Home Page
To be more precise, I look for a proof that only requires the input graph excluding a fixed minor, \(K_5\) for example in the case of planar graphs. There are two proofs that I particularly like: one by Plotkin, Rao, and Smith [2] and another by Alon, Seymour, and Thomas [1], which work for any graph excluding a fixed minor. I will present both. The central concept is a \(K_h\)-minor model.
Figure 1: A graph (left) and its \(K_5\)-minor model (right).
A balanced separator of a graph \(G = (V,E)\) is a subset of vertices \(S\subseteq V\) such that every connected component of \(G\setminus S\) has size at most \(2n/3\). There is nothing special about the constant \(2/3\); any constant smaller than \(1\), for example \(4/5\), works. In some places of this post, we will be handwavy on the constant.
About me - Hung Le / Home Page