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 , pp. 367-378(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_35).

Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_35
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1270

Actions (login required)

View Item View Item