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