  The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent
descriptive complexity of the graph. While originally derived from a
combinatorial graph isomorphism test called the Weisfeiler-Leman algorithm, the
WL dimension can also be characterised in terms of the number of variables that
is required to describe the graph up to isomorphism in first-order logic with
counting quantifiers.
  It is known that the WL dimension is upper-bounded for all graphs that
exclude some fixed graph as a minor (Grohe, JACM 2012). However, the bounds
that can be derived from this general result are astronomic. Only recently, it
was proved that the WL dimension of planar graphs is at most 3 (Kiefer,
Ponomarenko, and Schweitzer, LICS 2017).
  In this paper, we prove that the WL dimension of graphs embeddable in a
surface of Euler genus $g$ is at most $4g+3$. For the WL dimension of graphs
embeddable in an orientable surface of Euler genus $g$, our approach yields an
upper bound of $2g+3$.
