- Inapproximability of orthogonal compaction.
M. J. Bannister, D. Eppstein, and J. Simons.
arXiv:1108.4705.
J. Graph Algorithms and Applications 16 (3): 651–673, 2012. (Special issue for GD 2011.)This is the journal version of "Hardness of approximate compaction for nonplanar orthogonal graph drawings". It has stronger inapproximability bounds, and more variations of the compaction problem that are hard to approximate. In addition it includes a retraction of a buggy approximation algorithm from the conference version.