Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Drawing Planar Graphs

  • Conference paper
  • First Online:
WALCOM: Algorithms and Computation (WALCOM 2020)

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

Included in the following conference series:

  • 678 Accesses

Abstract

A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed planar embedding in the plane. A drawing problem X for a plane graph G asks to determine whether G has a drawing D satisfying a set P of given properties and to find D if it exists. The corresponding problem for a planar graph G asks to determine whether G has a planar embedding \(\varGamma \) such that \(\varGamma \) has a drawing D satisfying the set P of properties and find D if it exists. If every embedding of G has a drawing D satisfying P, then the problem is trivial, i.e., the problem for plane graphs and that for planar graphs are the same. Otherwise, the problem for planar graphs becomes difficult even if an efficient solution of the problem for a plane graph exists since a planar graph may have an exponential number of planar embeddings. Various techniques are found in literature that are used to solve the drawing problems for planar graphs. In this paper we review three of the widely used techniques, namely, (i) reduction to planarity testing, (ii) incremental modification and (iii) SPQR-tree decomposition.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 74.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Angelini, P., et al.: Testing planarity of partially embedded graphs. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 202–221. SIAM (2010)

    Google Scholar 

  2. Angelini, P., Colasante, E., Di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5–35 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. Angelini, P., Di Battista, G., Patrignani, M.: Finding a minimum-depthembedding of a planar graph in O(\(n^4\)) time. Algorithmica 60(4), 890–937 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  4. Angelini, P., et al.: Monotone drawings of graphs with fixed embedding. Algorithmica 71(2), 233–257 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bienstock, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica 5(1–4), 93–109 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  6. Boyer, J.M., Cortese, P.F., Patrignani, M., Di Battista, G.: Stop minding your P’s and Q’s: implementing a fast and simple DFS-based planarity testing and embedding algorithm. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 25–36. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24595-7_3

    Chapter  Google Scholar 

  7. Brandenburg, F.J.: 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421–438 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chang, Y.J., Yen, H.C.: On bend-minimized orthogonal drawings of planar 3-graphs. In: Proceedings of 33rd International Symposium on Computational Geometry (SoCG 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)

    Google Scholar 

  9. Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. Prog. Graph Theory 173, 153–173 (1984)

    MathSciNet  MATH  Google Scholar 

  10. De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  11. Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764–1811 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  12. Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. arXiv preprint, arXiv:1910.11782 (2019)

  14. Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings in quadratic time. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 481–494. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04414-5_34

    Chapter  Google Scholar 

  15. Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 201–216. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62495-3_49

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  17. Haeupler, B., Tarjan, R.E.: Planarity algorithms via PQ-trees. Electron. Notes Discret. Math. 31, 143–149 (2008)

    Article  MATH  Google Scholar 

  18. Hasan, M.M., Rahman, M.S.: No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract). In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 254–265. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26176-4_21

    Chapter  Google Scholar 

  19. Hasan, M.M., Rahman, M.S., Karim, M.R.: Box-rectangular drawings of planar graphs. J. Graph Algorithms Appl. 17(6), 629–646 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  20. Hong, S., Tokuyama, T.: Algorithmics for beyond planar graphs. In: NII Shonan Meeting Seminar, no. 27, pp. 51–63 (2016)

    Google Scholar 

  21. Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM (JACM) 21(4), 549–568 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  22. Hossain, M., Mondal, D., Rahman, M., Salma, S.: Universal line-sets for drawing planar 3-trees. J. Graph Algorithms Appl. 17(2), 59–79 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  23. Hossain, M.I., Rahman, M.S.: Good spanning trees in graph drawing. Theor. Comput. Sci. 607, 149–165 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hossain, M.I., Rahman, M.S.: Straight-line monotone grid drawings of series-parallel graphs. Discrete Math. Algorithms Appl. 7(02), 1550007 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mehlhorn, K., Mutzel, P.: On the embedding phase of the hopcroft and tarjan planarity testing algorithm. Algorithmica 16(2), 233–242 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  26. Nishizeki, T., Rahman, M.S.: Planar Graph Drawing, vol. 12. World Scientific Publishing Company, Singapore (2004)

    Book  MATH  Google Scholar 

  27. Rahman, M.S.: Basic Graph Theory. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-49475-3

    Book  MATH  Google Scholar 

  28. Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. Inform. Syst. 88(1), 23–30 (2005)

    Article  MATH  Google Scholar 

  29. Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comput. Geom. 10(3), 203–220 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  30. Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3, 31–62 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  31. Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular drawings of plane graphs without designated corners. Comput. Geom. 21(3), 121–138 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  32. Rahman, M.S., Nishizeki, T.: Bend-minimum orthogonal drawings of plane 3-graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Kučera, L. (eds.) WG 2002. LNCS, vol. 2573, pp. 367–378. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36379-3_32

    Chapter  Google Scholar 

  33. Rahman, M.S., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. J. Algorithms 50(1), 62–78 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  34. Samee, M.A.H., Alam, M.J., Adnan, M.A., Rahman, M.S.: Minimum segment drawings of series-parallel graphs with the maximum degree three. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 408–419. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00219-9_40

    Chapter  Google Scholar 

  35. Samee, M.A.H., Rahman, M.S.: Upward planar drawings of series-parallel digraphs with maximum degree three. In: Proceedings of WALCOM 2007, pp. 28–45. Bangladesh Academy of Sciences (2007)

    Google Scholar 

  36. Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138–148. Society for Industrial and Applied Mathematics (1990)

    Google Scholar 

  37. Shih, W.K., Hsu, W.L.: A new planarity test. Theor. Comput. Sci. 223(1), 179–192 (1999)

    MathSciNet  MATH  Google Scholar 

  38. Sultana, S., Rahman, M.S., Roy, A., Tairin, S.: Bar 1-visibility drawings of 1-planar graphs. In: Gupta, P., Zaroliagis, C. (eds.) ICAA 2014. LNCS, vol. 8321, pp. 62–76. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04126-1_6

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  40. Thomassen, C.: Planarity and duality of finite and infinite graphs. J. Comb. Theory Ser. B 29(2), 244–271 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  41. Thomassen, C.: Plane representations of graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory. Academic Press, New York (1984)

    MATH  Google Scholar 

  42. Tutte, W.T.: Convex representations of graphs. Proc. London Math. Soc. 3(1), 304–320 (1960)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgement

We thank Debajyoti Mondal and Shin-ichi Nakano for their useful comments on the manuscript of this paper.

Author information

Authors and Affiliations

  1. Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, 1000, Bangladesh

    Md. Saidur Rahman

  2. Department of Computer Science and Engineering, University of Dhaka, Dhaka, 1000, Bangladesh

    Md. Rezaul Karim

Authors
  1. Md. Saidur Rahman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Md. Rezaul Karim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Md. Saidur Rahman .

Editor information

Editors and Affiliations

  1. Department of CSE, BUET, Dhaka, Bangladesh

    M. Sohel Rahman

  2. Mathematical Informatics, University of Tokyo, Tokyo, Japan

    Kunihiko Sadakane

  3. School of Computing, National University of Singapore, Singapore, Singapore

    Wing-Kin Sung

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rahman, M.S., Karim, M.R. (2020). Drawing Planar Graphs. In: Rahman, M., Sadakane, K., Sung, WK. (eds) WALCOM: Algorithms and Computation. WALCOM 2020. Lecture Notes in Computer Science(), vol 12049. Springer, Cham. https://doi.org/10.1007/978-3-030-39881-1_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-39881-1_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-39880-4

  • Online ISBN: 978-3-030-39881-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation