Orthogonal-Ordering Constraints are Tough

Ulrik Brandes; Barbara Pampel

doi:10.7155/jgaa.00281

Orthogonal-Ordering Constraints are Tough

Authors

Ulrik Brandes
Barbara Pampel

DOI:

https://doi.org/10.7155/jgaa.00281

Keywords:

graph drawing , orthogonal ordering constraints , straight-line drawing

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.

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2013-01-01

How to Cite

Brandes, U., & Pampel, B. (2013). Orthogonal-Ordering Constraints are Tough. Journal of Graph Algorithms and Applications, 17(1), 1–10. https://doi.org/10.7155/jgaa.00281