Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models

Abstract

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 ∈ N , 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.