Bounding generalized coloring numbers of planar graphs using coin models

01/23/2022
by   Jesper Nederlof, et al.
0

We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and ordering the vertices by non-increasing radii of the associated discs. We prove that for every d∈ℕ, any such ordering has d-admissibility bounded by O(d/ln d) and weak d-coloring number bounded by O(d^4 ln d). This in particular shows that the d-admissibility of planar graphs is bounded by O(d/ln d), which asymptotically matches a known lower bound due to Dvořák and Siebertz.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset