Orthogonal-Ordering Constraints are Tough - Brandes, Ulrik; Pampel, Barbara (Journal of Graph Algorithms and Applications, 2013)
We show that rectilinear graph drawing, the core problem of bend-minimum orthogonal graph drawing, and uniform edge-length drawing, the core problem of force-directed placement, are NP-hard even for embedded paths if subjected to orthogonal-ordering constraints.