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.
翻译:线性排列是从图 $G$ 的 $n$ 个顶点到 $n$ 个不同连续整数之间的映射 $\pi$。线性排列可以通过将顶点画在水平线上并将边画在该线上方的半圆中来表示。在此设置中,边的长度定义为其两个端点在排列中的位置差的绝对值,排列的代价定义为所有边长的总和。在本研究中,我们研究了最大线性排列问题(MaxLA)的两个变体,其中最大化代价的排列被认为是最优解。在线性树上进行计划变量中,必须以使得没有边交叉的方式安排图形的所有节点。在投影树中的计划变体中,排列必须是平面的,树的根节点不能被任何边覆盖。本文提出了一个使用线性时间和空间解决树形计划和投影MaxLA的算法。我们还证明了最大投影和平面排列的若干属性,并表明毛毛虫树最大化规划MaxLA,这超越了先前关于树的极端结果。