Inapproximability of Orthogonal Compaction
Michael J. Bannister, David Eppstein, Joseph A. Simons · Journal of Graph Algorithms and Applications · 2012
We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless P = NP. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.