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.