Orthogonal-Ordering Constraints are Tough
Vol. 17, no. 1, pp. 1-10, 2013. Concise paper.
Abstract 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.
Submitted: June 2010.
Reviewed: April 2011.
Revised: September 2012.
Accepted: November 2012.
Final: December 2012.
Published: January 2013.
Communicated by Giuseppe Di Battista
article (PDF)