Maximal Linear Arrangement is NP complete on Bipartite Graphs

Aparna Das, Jonathan Needleman

The linear arrangement of a simple graph $G=(V,E)$ is a bijective labeling $\pi$ of the vertices of $G$ to the set $\{1,\dots ,n\}$. The maximum linear arrangement ($\texttt{maxL…