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.