Inapproximability of Orthogonal Compaction

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.

Updated to the final version to appear in the Journal of Graph Algorithms and Applications

Cited by in corpus (2)

• Minimum Rectilinear Polygons for Given Angle Sequences
• Parameterized Approaches to Orthogonal Compaction