Maximum linear arrangement of directed graphs

We study a new problem on digraphs, Maximum Directed Linear Arrangement (MaxDLA). This is a directed and maximization variant of the well-studied Minimum Linear Arrangement (MinLA) problem. We relate MaxDLA to the Maximum Directed Cut (MaxDiCut) problem by bounding each in terms of the other. We prove that both MaxDiCut and MaxDLA are NP-Hard for planar digraphs. By contrast, the undirected Maximum Cut problem is known to be polynomial on planar graphs. We present a polynomial algorithm solving MaxDLA on orientations of bounded-degree trees, and, as a by-product, a polynomial algorithm for MinLA on graphs $G$ when $\overline{G}$ is a bounded-degree tree. This complements the known fact that MinLA is polynomial-time solvable on trees. Finally, we study maximization analogues of Harper's celebrated isoperimetric inequality for hypercubes. We study tournaments, orientations of graphs with maximum degree at most two, and transitive acyclic digraphs.