Asymptotically Optimal Vertex Ranking of Planar Graphs
share
A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph G with integer colours so that for any path u_0,…,u_p of length at most ℓ, φ(u_0)≠φ(u_p) or φ(u_0)<max{φ(u_0),…,φ(u_p)}. We show that, for any fixed integer ℓ≥ 2, every n-vertex planar graph has an ℓ-ranking using O(log n/logloglog n) colours and this is tight even when ℓ=2; for infinitely many values of n, there are n-vertex planar graphs, for which any 2-ranking requires Ω(log n/logloglog 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 ℓ-ranking graphs of treewidth t and graphs of simple treewidth t. These upper bounds are constructive and give O(nlog n)-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for ℓ-rankings of apex minor-free graphs and k-planar graphs.
READ FULL TEXT