Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings

We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows or the minimum possible area cannot be approximated to within better than a polynomial factor in polynomial time unless P = NP. However, there is a fixed-parameter tractable algorithm for testing whether a drawing can be compacted to a given number of rows