Processing math: 100%
Op­ti­mal Ad­ja­cency-La­belling Schemes for Pla­nar Graphs
Pat Morin
Car­leton Uni­ver­sity

We show that there ex­ists an ad­ja­cency la­belling scheme for pla­nar graphs where each ver­tex of an n-ver­tex pla­nar graph is as­signed a (\log n+o(\log n))-bit label. This is op­ti­mal up to the lower-order term. This re­sult ex­tends to a much larger class of graphs, namely any sub­graph of a strong prod­uct H\boxtimes P where H is a graph of bounded treewidth and P is a path. This class in­cludes bounded-genus graphs and k-pla­nar graphs.