Inapproximability of Orthogonal Compaction
Michael J. Bannister, David Eppstein, and Joseph A. Simons
Vol. 16, no. 3, pp. 651-673, 2012. Regular paper.
Abstract 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.
Submitted: November 2011.
Reviewed: February 2012.
Revised: February 2012.
Accepted: February 2012.
Final: March 2012.
Published: September 2012.
article (PDF)