# Minimum projective linearizations of trees in linear time

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 21 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [A correction on Shiloach's algorithm for minimum linear arrangement of trees](https://mlsanity.com/paper/1511.01061/) (2015)

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

- [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)
- [The optimal placement of the head in the noun phrase. The case of demonstrative, numeral, adjective and noun](https://mlsanity.com/paper/2402.10311/) (2024)
- [The expected sum of edge lengths in planar linearizations of trees. Theory and applications](https://mlsanity.com/paper/2207.05564/) (2022)
- [Better Benchmarking LLMs for Zero-Shot Dependency Parsing](https://mlsanity.com/paper/2502.20866/) (2025)
- [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)
- [Dependency distance minimization predicts compression](https://mlsanity.com/paper/2109.08900/) (2021)
- [The Maximum Linear Arrangement Problem for trees under projectivity and planarity](https://mlsanity.com/paper/2206.06924/) (2022)

## Abstract (arXiv)

The Minimum Linear Arrangement problem (MLA) consists of finding a mapping π from vertices of a graph to distinct integers that minimizes sum_u,v∈ E|π(u) - π(v)|. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in n=|V|. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward O(n)-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in O(n) but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT's algorithm runs in O(n log dmax) where dmax is the maximum degree but did not provide sufficient detail. Here we correct an error in HS's algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in O(n) time.