**Hardness of approximate compaction for nonplanar orthogonal graph drawings**.

M. J. Bannister and D. Eppstein.

*Proc. 19th Int. Symp. Graph Drawing*, Eindhoven, The Netherlands, 2011.

Springer,*Lecture Notes in Comp. Sci.*7034, 2012, pp. 367–378.We show that, for several variants of the problem of compacting a grid drawing of a graph to use the minimum number of rows or minimum area, no good approximation algorithm is possible. We also develop fixed-parameter tractable algorithms and approximation algorithms showing that some of our inapproximability bounds are tight. See the journal version, "Inapproximability of orthogonal compaction", for some improvements and corrections.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.