A linear arrangement is a mapping $\pi$ from the $n$ vertices of a graph $G$
to $n$ distinct consecutive integers. Linear arrangements can be represented by
drawing the vertices along a horizontal line and drawing the edges as
semicircles above said line. In this setting, the length of an edge is defined
as the absolute value of the difference between the positions of its two
vertices in the arrangement, and the cost of an arrangement as the sum of all
edge lengths. Here we study two variants of the Maximum Linear Arrangement
problem (MaxLA), which consists of finding an arrangement that maximizes the
cost. In the planar variant for free trees, vertices have to be arranged in
such a way that there are no edge crossings. In the projective variant for
rooted trees, arrangements have to be planar and the root of the tree cannot be
covered by any edge. In this paper we present algorithms that are linear in
time and space to solve planar and projective MaxLA for trees. We also prove
several properties of maximum projective and planar arrangements, and show that
caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby
generalizing a previous extremal result on trees.

本文研究了最大线性排列问题（MaxLA）的两个变体，即基于免费树和基于根树的平面和投影变体。针对树的平面和投影 MaxLA 问题，提出了相应的线性时间和空间的算法，并证明了最大投影和平面排列的几个性质，同时表明毛毛虫树是平面 MaxLA 问题中所有尺寸固定的树中最优的，从而推广了前人在树上的极值结果。