CS 269S, Fall 2011: Theory Seminar
DBH 1433
21 October 2011:

Speaker: Michael Bannister

Title: Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings

Abstract: We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows or the minimum possible area cannot be approximated to within better than a polynomial factor in polynomial time unless P = NP. However, there is a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a given number of rows.