Asymptotically Optimal Vertex Ranking of Planar Graphs

Abstract: A (vertex)

e l l

-ranking is a colouring

v a r p h i : V (G) o m a t h b b N

of the vertices of a graph

G

with integer colours so that for any path

u_{0}, l d o t s, u_{p}

of length at most

e l l

,

v a r p h i (u_{0}) e q v a r p h i (u_{p})

or

v a r p h i (u_{0}) < m a x v a r p h i (u_{0}), l d o t s, v a r p h i (u_{p})

. We show that, for any fixed integer

e l l g e 2

, every

n

-vertex planar graph has an

e l l

-ranking using

O (l o g n / l o g l o g l o g n)

colours and this is tight even when

e l l = 2

; for infinitely many values of

n

, there are

n

-vertex planar graphs, for which any 2-ranking requires

O m e g a (l o g n / l o g l o g l o g 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

e l l

-ranking graphs of treewidth

t

and graphs of simple treewidth

t

. These upper bounds are constructive and give

O (n)

-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for

e l l

-rankings of apex minor-free graphs and

k

-planar graphs.

This page was built for publication: Asymptotically Optimal Vertex Ranking of Planar Graphs