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.

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
ID Code:1270

Repository Staff Only: item control page

References

Biedl, T.C., Madden, B.P., Tollis, I.G.: The three-phase method: a unified approach to orthogonal graph drawing. Int. J. Comput. Geom. Appl. 10(6), 553–580 (2000), doi:10.1142/S0218195900000310

Bridgeman, S.S., Di Battista, G., Didimo, W., Liotta, G., Tamassia, R., Vismara, L.: Turn-regularity and optimal area drawings of orthogonal representations. Computational Geometry: Theory and Applications 16(1), 53–93 (2000), doi:10.1016/S0925-7721(99)00054-1

Eades, P., Hong, S.-H., Poon, S.-H.: On Rectilinear Drawing of Graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 232–243. Springer, Heidelberg (2010), doi:10.1007/978-3-642-11805-0 23

Eiglsperger, M., Fekete, S.P., Klau, G.W.: Orthogonal Graph Drawing. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 121–171. Springer, Heidelberg (2001), doi:10.1007/3-540-44969-8 6

Eppstein, D.: The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 78–89. Springer, Heidelberg (2009), doi:10.1007/978-3-642-00219-9 9

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: IEEE Pacific Visualization Symposium (PacificVIS 2008), pp. 41–46 (2008), doi:10.1109/PACIFICVIS.2008.4475457

Lick, D.R., White, A.T.: k-degenerate graphs. Canadian Journal of Mathematics 22, 1082–1096 (1970), doi:10.4153/CJM-1970-125-1

Mañuch, J., Patterson, M., Poon, S.-H., Thachuk, C.: Complexity of Finding Non-Planar Rectilinear Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 305–316. Springer, Heidelberg (2011), doi:10.1007/978-3-642-18469-7 28

Patrignani, M.: On the complexity of orthogonal compaction. Computational Geometry 19(1), 47–67 (2001), doi:10.1016/S0925-7721(01)00010-4

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987), doi:10.1137/0216030

Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing 3(1), 103–128 (2007), doi:10.4086/toc.2007.v003a006