  We study the shapes of all Newton-Okounkov bodies $\Delta_{v}(D)$ of a given
big divisor $D$ on a surface $S$ with respect to all rank 2 valuations $v$ of
$K(S)$. We obtain upper bounds for, and in many cases we determine exactly, the
possible numbers of vertices of the bodies $\Delta_{v}(D)$. The upper bounds
are expressed in terms of Picard numbers and they are birationally invariant,
as they do not depend on the model $\tilde{S}$ where the valuation $v$ becomes
a flag valuation. We also conjecture that the set of all Newton-Okounkov bodies
of a single ample divisor $D$ determines the Picard number of $S$, and prove
that this is the case for Picard number 1, by an explicit characterization of
surfaces of Picard number 1 in terms of Newton-Okounkov bodies.
