Optimal Adjacency-Labelling Schemes for Planar Graphs
Pat Morin
Carleton University
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$-vertex planar graph is assigned a $(\log n+o(\log n))$-bit label. This is optimal up to the lower-order term. This result extends to a much larger class of graphs, namely any subgraph of a strong product $H\boxtimes P$ where $H$ is a graph of bounded treewidth and $P$ is a path. This class includes bounded-genus graphs and $k$-planar graphs.