David Eppstein - Publications

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