nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Drawing Planar Graphs

verfasst von : Md. Saidur Rahman, Md. Rezaul Karim

Erschienen in: WALCOM: Algorithms and Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Space Efficient Separator Algorithms for Planar Graphs

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)

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

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)MathSciNetMATHCrossRef

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

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

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_3CrossRef

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

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)

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

10.

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

11.

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

12.

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

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_34CrossRef

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_49CrossRef

16.

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

17.

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

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_21CrossRef

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)MathSciNetMATHCrossRef

20.

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

21.

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

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)MathSciNetMATHCrossRef

23.

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

24.

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

25.

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

26.

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

27.

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

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)MATHCrossRef

29.

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

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)MathSciNetMATHCrossRef

31.

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

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_32CrossRef

33.

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

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_40CrossRef

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)

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)

37.

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

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_6CrossRef

39.

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

40.

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

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

42.

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

Titel: Drawing Planar Graphs
verfasst von: Md. Saidur Rahman
Md. Rezaul Karim
Verlag: Springer International Publishing
Buch: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"