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 () 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 (), the counterpart of . We devise a new characterization of maximum arrangements of general graphs, and prove that can be solved for k -regular graphs ( $$k\le 2$$ k ≤ 2 ) in time $$O{\left( n\right) }$$ O n , and for k -linear trees ( $$k\le 2$$ k ≤ 2 ) in time $$O{\left( n\right) }$$ O n . We present two constrained variants of we call and . We prove that the former can be solved in time $$O{\left( n\right) }$$ O n for any connected bipartite graph; the latter can be solved by an algorithm that typically runs in time $$O{\left( n^3\log n\right) }$$ O n 3 log n on unlabeled trees. We show that is a 3/2-approximation algorithm for for trees.