  A labeling scheme for nearest common ancestors assigns a distinct binary
string, called the label, to every node of a tree, so that given the labels of
two nodes (and no further information about the topology of the tree) we can
compute the label of their nearest common ancestor. The goal is to make the
labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor.
Comput. Syst. 37(3):441-456 2004] showed that $O(\log n)$-bit labels are
enough. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this
to only $2.772\log n$, and provided a lower bound of $1.008\log n$.
  We connect designing a labeling scheme for nearest common ancestors to the
existence of a tree, called a minor-universal tree, that contains every tree on
$n$ nodes as a topological minor. Even though it is not clear if a labeling
scheme must be based on such a notion, we argue that the existing schemes can
be reformulated as such, and it allows us to obtain clean and good bounds on
the length of the labels. As the main upper bound, we show that $2.318\log
n$-bit labels are enough. Surprisingly, the notion of a minor-universal tree
for binary trees on $n$ nodes has been already used in a different context by
Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3):416-435, 1999]
introduced a closely related notion of a universal tree. On the lower bound
side, we show that the size of any minor-universal tree for trees on $n$ nodes
is $\Omega(n^{2.174})$. This highlights a natural limitation for all approaches
based on such trees. Our lower bound technique also implies that the size of
any universal tree in the sense of Young et al. is $\Omega(n^{2.185})$, thus
dramatically improves their lower bound of $\Omega(n\log n)$. We complement the
existential results with a generic transformation that decreases the query time
to constant in any scheme based on a minor-universal tree.
