Planar graphs in blowups of fans
<|reference_start|>Planar graphs in blowups of fans: We show that every $n$-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O(\sqrt{n}\log^2 n)$. Equivalently, every $n$-vertex planar graph $G$ has a set $X$ of $O(\sqrt{n}\log^2 n)$ vertices such that $G-X$ has bandwidth $O(\sqrt{n}\log^2 n)$. This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and $k$-planar graphs for fixed $k$. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every $n$-vertex planar graph $G$ has a set of $O((n\log n)/D)$ vertices whose removal results in a graph with local density at most $D$. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.<|reference_end|>
@article{dujmović2024planar,
    title={Planar graphs in blowups of fans},
    author={Vida Dujmovi'c, Gwena"el Joret, Piotr Micek, Pat Morin, and David R.
  Wood},
    journal={arXiv preprint arXiv:2407.05936},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05936},
    primaryClass={math.CO cs.DM}
}