  An \emph{adjacency labeling scheme} for a given class of graphs is an
algorithm that for every graph $G$ from the class, assigns bit strings (labels)
to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are
adjacent can be determined by a fixed procedure that examines only their
labels. It is known that planar graphs with $n$ vertices admit a labeling
scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve
this bound by designing a labeling scheme with labels of bit length
$(\frac{4}{3}+o(1))\log{n}$. In graph-theoretical terms, this implies an
explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all
planar graphs on $n$ vertices as induced subgraphs, improving the previous best
upper bound of $n^{2+o(1)}$. Our scheme generalizes to graphs of bounded Euler
genus with the same label length up to a second-order term. All the labels of
the input graph can be computed in polynomial time, while adjacency can be
decided from the labels in constant time.
