David Eppstein - Publications

• 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.

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

Semi-automatically filtered from a common source file.