Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Complexity of Finding Non-Planar Rectilinear Drawings of Graphs

  • Conference paper
Graph Drawing(GD 2010)

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6502))

Included in the following conference series:

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.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. 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)

    Chapter  Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. 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)

    Chapter  Google Scholar 

  4. 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)

    Article MathSciNet MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  11. 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)

    Chapter  Google Scholar 

  12. 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)

    Chapter  Google Scholar 

  13. 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)

    Article MathSciNet MATH  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of British Columbia, Vancouver, BC, Canada

    Ján Maňuch, Murray Patterson & Chris Thachuk

  2. Dept. of Mathematics, Simon Fraser University, Burnaby, BC, Canada

    Ján Maňuch

  3. Dept. of Computer Science, National Tsing Hua University, Taiwan, R.O.C.

    Sheung-Hung Poon

Authors
  1. Ján Maňuch

    You can also search for this author inPubMed Google Scholar

  2. Murray Patterson

    You can also search for this author inPubMed Google Scholar

  3. Sheung-Hung Poon

    You can also search for this author inPubMed Google Scholar

  4. Chris Thachuk

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer and Information Science, University of Konstanz, Konstanz, Germany

    Ulrik Brandes  & Sabine Cornelsen  & 

Rights and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Maňuch, J., Patterson, M., Poon, SH., Thachuk, C. (2011). Complexity of Finding Non-Planar Rectilinear Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds) Graph Drawing. GD 2010. Lecture Notes in Computer Science, vol 6502. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18469-7_28

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp