×

Orthogonal-ordering constraints are tough. (English) Zbl 1256.05156

Summary: 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 \(\mathcal {NP}\)-hard even for embedded paths if subjected to orthogonal-ordering constraints.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI