  Dependency trees have proven to be a very successful model to represent the
syntactic structure of sentences of human languages. In these structures,
vertices are words and edges connect syntactically-dependent words. The
tendency of these dependencies to be short has been demonstrated using random
baselines for the sum of the lengths of the edges or its variants. A ubiquitous
baseline is the expected sum in projective orderings (wherein edges do not
cross and the root word of the sentence is not covered by any edge), that can
be computed in time $O(n)$. Here we focus on a weaker formal constraint, namely
planarity. In the theoretical domain, we present a characterization of
planarity that, given a sentence, yields either the number of planar
permutations or an efficient algorithm to generate uniformly random planar
permutations of the words. We also show the relationship between the expected
sum in planar arrangements and the expected sum in projective arrangements. In
the domain of applications, we derive a $O(n)$-time algorithm to calculate the
expected value of the sum of edge lengths. We also apply this research to a
parallel corpus and find that the gap between actual dependency distance and
the random baseline reduces as the strength of the formal constraint on
dependency structures increases, suggesting that formal constraints absorb part
of the dependency distance minimization effect. Our research paves the way for
replicating past research on dependency distance minimization using random
planar linearizations as random baseline.
