Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs

Abstract

Linear arrangements of graphs are a well-known type of graph labeling and are found in many important computational problems. A linear arrangement is usually defined as a permutation of the $n$ vertices of a graph. An intuitive geometric setting is that of vertices lying on consecutive integer positions in the real line, starting at 1; edges are often drawn as semicircles above the real line. A well-known computational problem is the Minimum Linear Arrangement Problem ($\mathtt{minLA}$) where the goal is to find an arrangement that minimizes the sum of edge lengths. In this paper we study the Maximum Linear Arrangement problem ($\mathtt{MaxLA}$), the counterpart of $\mathtt{minLA}$. We devise a new characterization of maximum arrangements of general graphs, and prove that $\mathtt{MaxLA}$ can be solved for $k$-regular graphs ($k\le 2$) in time $O(n)$, and for $k$-linear trees ($k\le 2$) in time $O(n)$. We present two constrained variants of $\mathtt{MaxLA}$ we call $\mathtt{bipartiteMaxLA}$ and $1-\mathtt{thistleMaxLA}$. We prove that the former can be solved in time $O(n)$ for any connected bipartite graph; the latter can be solved by an algorithm that typically runs in time $O(n^3\log n)$ on unlabeled trees. We show that $\mathtt{bipartiteMaxLA}$ is a $3/2$-approximation algorithm for $\mathtt{MaxLA}$ for trees.