Planar graphs (and related families of graphs) have \((1+o(1))\log n\)-bit adjacency labelling schemes. Equivalently, there is a graph with \(n^{1+o(1)}\) vertices that contains every \(n\)-vertex planar graph as an induced subgraph.

The proof combines our year-old product structure theorem with binary search trees!

· · Web · 0 · 2 · 4
Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!