Planar Universal Graphs

Neal Brand and Margaret Morton


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.

planar, infinite, universal, random

Math Review Classification

Last Updated

24 pages

This article is available in: