Hardness of Approximate Compaction for Nonplanar Orthogonal Graph DrawingsBannister, 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 , pp. 367-378(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_35). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_35
AbstractWe 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.
Actions (login required)
|