2023/12/07 by Lluís Alemany-Puig, Alemany-Puig, Lluís, Juan Luis Esteban +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2312.04487
openalex publication_date 2023/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (\tt 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 (\tt MaxLA), the counterpart of \tt minLA. We devise a new characterization of maximum arrangements of general graphs, and prove that \tt MaxLA can be solved for k-regular graphs (k≤2) in time O(n), and for k-linear trees (k≤2) in time O(n). We present two constrained variants of \tt MaxLA we call \tt bipartite MaxLA and \tt 1-thistle MaxLA. 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(n3log n) on unlabeled trees. We show that \tt bipartite MaxLA is a 3/2-approximation algorithm for \tt MaxLA for trees.