Bandwidth, treewidth, separators, expansion, and universality
Böttcher, J.
, Pruessmann, K. P., Taraz, A. & Würfl, A.
(2008).
Bandwidth, treewidth, separators, expansion, and universality.
Electronic Notes in Discrete Mathematics,
31, 91-96.
https://doi.org/10.1016/j.endm.2008.06.018
, Pruessmann, K. P., Taraz, A. & Würfl, A.
(2008).
Bandwidth, treewidth, separators, expansion, and universality.
Electronic Notes in Discrete Mathematics,
31, 91-96.
https://doi.org/10.1016/j.endm.2008.06.018
We prove that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence for each γ>0 every n-vertex graph with minimum degree (3/4+γ)n source contains a copy of every bounded-degree planar graph on n vertices. The proof relies on the fact that planar graphs have small separators. Indeed, we show more generally that for any class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent.