  We propose a new arrangement problem on directed graphs, Maximum Directed
Linear Arrangement (MaxDLA). This is a directed variant of a similar problem
for undirected graphs, in which however one seeks maximum and not minimum; this
problem known as the Minimum Linear Arrangement Problem (MinLA) has been much
studied in the literature. We establish a number of theorems illustrating the
behavior and complexity of MaxDLA. First, we relate MaxDLA to Maximum Directed
Cut (MaxDiCut) by proving that every simple digraph $D$ on $n$ vertices
satisfies $\frac{n}{2}$$maxDiCut(D) \leq MaxDLA(D) \leq (n-1)MaxDiCut(D)$.
Next, we prove that MaxDiCut is NP-Hard for planar digraphs (even with the
added restriction of maximum degree 15); it follows from the above bounds that
MaxDLA is also NP-Hard for planar digraphs. In contrast, Hadlock (1975) and
Dorfman and Orlova (1972) showed that the undirected Maximum Cut problem is
solvable in polynomial time on planar graphs.
  On the positive side, we present a polynomial-time algorithm for solving
MaxDLA on orientations of trees with degree bounded by a constant, which
translates to a polynomial-time algorithm for solving MinLA on the complements
of those trees. This pairs with results by Goldberg and Klipker (1976),
Shiloach (1979) and Chung (1984) solving MinLA in polynomial time on trees.
Finally, analogues of Harper's famous isoperimetric inequality for the
hypercube, in the setting of MaxDLA, are shown for tournaments, orientations of
graphs with degree at most two, and transitive acyclic digraphs.
