# The expected sum of edge lengths in planar linearizations of trees. Theory and applications

arXiv: https://arxiv.org/abs/2207.05564 · HTML: https://mlsanity.com/paper/2207.05564/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 9 of 9)

- [The optimality of syntactic dependency distances](https://mlsanity.com/paper/2007.15342/) (2020)
- [Anti dependency distance minimization in short sequences. A graph theoretic approach](https://mlsanity.com/paper/1906.05765/) (2019)
- [Minimum projective linearizations of trees in linear time](https://mlsanity.com/paper/2102.03277/) (2021)
- [The risks of mixing dependency lengths from sequences of different length](https://mlsanity.com/paper/1304.3841/) (2013)
- [The scarcity of crossing dependencies: a direct outcome of a specific constraint?](https://mlsanity.com/paper/1601.03210/) (2016)
- [Are crossing dependencies really scarce?](https://mlsanity.com/paper/1703.08324/) (2017)
- [Memory limitations are hidden in grammar](https://mlsanity.com/paper/1908.06629/) (2019)
- [Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees](https://mlsanity.com/paper/2107.03277/) (2021)
- [The Linear Arrangement Library. A new tool for research on syntactic dependency structures](https://mlsanity.com/paper/2112.02512/) (2021)

## Built on by (most cited first, 2 of 2)

- [Who is the root in a syntactic dependency structure?](https://mlsanity.com/paper/2501.15188/) (2025)
- [How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization](https://mlsanity.com/paper/2604.01938/) (2026)

## Abstract (arXiv)

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.