Planar Universal Graphs

Abstract

A graph is g-universal if it satisfies two conditions. First it must contain a subdivision of every proper planar graph of degree at most three as a subgraph. Second, the function g puts a restriction on the subdivision. In particular, for a planar graph H of degree at most three, a fixed vertex $w_0$ of H, and an arbitrary vertex w of H, the images of the vertices $w_0$ and w in the universal graph are no more than $g(d(w_0, w))$ apart. We show that a large class of planar graphs are $O(n^3)4-universal.