Top

Published in:

2016 | OriginalPaper | Chapter

1-Bend Upward Planar Drawings of SP-Digraphs

Authors : Emilio Di Giacomo, Giuseppe Liotta, Fabrizio Montecchiani

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is proved that every series-parallel digraph whose maximum vertex-degree is \(\varDelta \) admits an upward planar drawing with at most one bend per edge such that each edge segment has one of \(\varDelta \) distinct slopes. This is shown to be worst-case optimal in terms of the number of slopes. Furthermore, our construction gives rise to drawings with optimal angular resolution \(\frac{\pi }{\varDelta }\). A variant of the proof technique is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) one-bend planar drawing with \(\lceil \frac{\varDelta }{2}\rceil \) distinct slopes if biconnected, and with \(\lceil \frac{\varDelta }{2}\rceil +1\) distinct slopes if connected.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Computing NodeTrix Representations of Clustered Graphs

next chapter Non-aligned Drawings of Planar Graphs

Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132–169 (1998)MathSciNetCrossRefMATH

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)MathSciNetCrossRefMATH

Binucci, C., Didimo, W., Giordano, F.: Maximum upward planar subgraphs of embedded planar digraphs. Comput. Geom. 41(3), 230–246 (2008)MathSciNetCrossRefMATH

Czyzowicz, J.: Lattice diagrams with few slopes. J. Comb. Theory Ser. A 56(1), 96–108 (1991). http://dx.doi.org/10.1016/0097-3165(91)90025-C MathSciNetCrossRefMATH

Czyzowicz, J., Pelc, A., Rival, I.: Drawing orders with few slopes. Discret. Math. 82(3), 233–250 (1990). http://dx.doi.org/10.1016/0012-365X(90)90201-R MathSciNetCrossRefMATH

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Upper Saddle River (1999)MATH

Di Giacomo, E., Liotta, G., Montecchiani, F.: 1-Bend Upward Planar Drawings of SP-Digraphs. ArXiv e-prints abs/1608.08425 (2016). http://arxiv.org/abs/1608.08425v1

Di Giacomo, E.: Drawing series-parallel graphs on restricted integer 3D grids. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 238–246. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24595-7_22 CrossRef

Di Giacomo, E., Liotta, G., Montecchiani, F.: The planar slope number of subcubic graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 132–143. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54423-1_12 CrossRef

10.

Di Giacomo, E., Liotta, G., Montecchiani, F.: Drawing outer 1-planar graphs with few slopes. J. Graph. Algorithms Appl. 19(2), 707–741 (2015). http://dx.doi.org/10.7155/jgaa.00376 MathSciNetCrossRefMATH

11.

Didimo, W.: Upward planar drawings and switch-regularity heuristics. J. Graph Algorithms Appl. 10(2), 259–285 (2006)MathSciNetCrossRefMATH

12.

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discret. Math. 23(4), 1842–1899 (2009)MathSciNetCrossRefMATH

13.

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

14.

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesar, M., Vyskocil, T.: The planar slope number of planar partial 3-trees of bounded degree. Gr. Combin. 29(4), 981–1005 (2013)MathSciNetCrossRefMATH

15.

Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM J. Discret. Math. 27(2), 1171–1183 (2013)MathSciNetCrossRefMATH

16.

Knauer, K., Walczak, B.: Graph drawings with one bend and few slopes. In: Kranakis, E., Navarro, G., Chávez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 549–561. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49529-2_41 CrossRef

17.

Knauer, K.B., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. Comput. Geom. 47(5), 614–624 (2014)MathSciNetCrossRefMATH

18.

Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 412–423. Springer, Heidelberg (2013). doi:10.1007/978-3-319-03841-4_36 CrossRef

19.

Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discr. Comput. Geom. 1, 343–353 (1986)MathSciNetCrossRefMATH

20.

Tamassia, R., Tollis, I.G.: A unified approach a visibility representation of planar graphs. Discr. Comput. Geom. 1, 321–341 (1986)MathSciNetCrossRefMATH

Title: 1-Bend Upward Planar Drawings of SP-Digraphs
Authors: Emilio Di Giacomo
Giuseppe Liotta
Fabrizio Montecchiani
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-50106-2_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner