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.

arxiv.org/abs/2003.04280

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

· · Web · · ·

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