us

Asymptotically optimal vertex ranking of planar graphs (and beyond)

A (vertex) $\ell$-ranking is a labelling $\varphi:V(G)\to\N$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,\ldots,u_p$ of length at most $\ell$, $\varphi(u_0)\neq\varphi(u_p)$ or $\varphi(u_0)<\max{\varphi(u_0),\ldots,\varphi(u_p)}$. We show that, for any fixed integer $\ell\ge 2$, every $n$-vertex planar graph has an $\ell$-ranking using $O(\log n/\log\log\log n)$ colours and this is tight even when $\ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $\Omega(\log n/\log\log\log n)$ colours. This result also extends to bounded genus graphs.

In developing this proof we obtain optimal bounds on the number of colours needed for $\ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(n\log n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $\ell$-rankings of apex minor-free graphs and $k$-planar graphs.