Planar cubic graphs of small diameter

Abstract

Cubic planar $n$-vertex graphs with faces of length at most $6$, e.g., fullerene graphs, have diameter in $\Omega (\sqrt{n})$. It has been suspected, that a similar result can be shown for cubic planar graphs with faces of bounded length. This note provides a family of cubic planar $n$-vertex graphs with faces of length at most $7$ and diameter in $O(\log n)$, thus refuting the above suspicion.

2 pages, 2 figures

References in corpus (1)

• Fullerene graphs of small diameter