Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
The paper in this page has been just accepted in JGAA and is in the queue for being assigned a volume and an issue number. It has been accepted by one of the JGAA editors and its content will no longer be modified. However, the publication format of the paper may still be subject to minor changes.
|
DOI: 10.7155/jgaa.00263 Inapproximability of Orthogonal Compaction Michael J. Bannister , David Eppstein , and Joseph A. Simons To be published in the Special Issue of GD 2011. Abstract We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless P=NP. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.
|
Posted here: March 2012. |
| Journal of Graph Algorithms and Applications |