Complexity of Finding Non-Planar Rectilinear Drawings of Graphs

Manuch, Jan and Patterson, Murray and Poon, Sheung-Hung and Thachuk, Chris (2011) Complexity of Finding Non-Planar Rectilinear Drawings of Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 305-316 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_28).

Full text not available from this repository.

Abstract

We study the complexity of the problem of finding non-planar rectilinear drawings of graphs. This problem is known to be NP-complete. We consider natural restrictions of this problem where constraints are placed on the possible orientations of edges. In particular, we show that if each edge has prescribed direction "left" , "right" , "down" or "up" , the problem of finding a rectilinear drawing is polynomial, while finding such a drawing with the minimum area is NP-complete. When assigned directions are "horizontal" or "vertical" or a cyclic order of the edges at each vertex is specified, the problem is NP-complete. We show that these two NP-complete cases are fixed parameter tractable in the number of vertices of degree 3 or 4.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_28
Classifications:P Styles > P.540 Planar
ID Code:1216

Repository Staff Only: item control page

References

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009)

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)

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)

Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Symvonis, A., Welzl, E., Woeginger, G.: Drawing graphs in the plane with high resolution. SIAM Journal on Computing 22(5), 1035–1052 (1993)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal of Computing 31(2), 601–625 (2001)

Hoffman, F., Kriegel, K.: Embedding rectilinear graphs in linear time. Information Processing Letters 29(2), 75–79 (1988)

Huang, W., Hong, S., Eades, P.: Effects of crossing angles. In: Proc. of IEEE Pacific Visualization Symposium (PacificVis 2008), pp. 41–46 (2008)

Opatrny, J.: Total ordering problem. SIAM Journal of Computing 8(1), 111–114 (1979)

Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)

Patrignani, M.: On the complexity of orthogonal compaction. Computational Geometry 19, 47–67 (2001)

Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 387–392. Springer, Heidelberg (2004)

Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of series-parallel graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 409–420. Springer, Heidelberg (2006)

Rahman, M.S., Naznin, M., Nishizeki, T.: Orthogonal drawings of plane graphs without bends. Journal of Graph Algorithms and Applications 7(4), 335–362 (2003)

Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM Journal of Computing 14(2), 355–372 (1985)