Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings
Bannister, Michael J. and Eppstein, David (2012) Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 367-378 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_35).
Full text not available from this repository.
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.
Repository Staff Only: item control page