Top

previous chapter Compact Layered Drawings of General Directed Gr...

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Bitonic st-orderings for Upward Planar Graphs

Read first chapter

Author: Martin Gronemann

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

Canonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. While st-orderings do extend to directed graphs, especially planar st-graphs, they do not offer the same properties as canonical orderings. In this work we extend the so called bitonic st-orderings to directed graphs. We fully characterize planar st-graphs that admit such an ordering and provide a linear-time algorithm for recognition and ordering. If for a graph no bitonic st-ordering exists, we show how to find in linear time a minimum set of edges to split such that the resulting graph admits one. With this new technique we are able to draw every upward planar graph on n vertices by using at most one bend per edge, at most \(n - 3\) bends in total and within quadratic area.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

This restriction is necessary due to the possible absence of the st-edge which is allowed by our definition of planar st-graphs.

Abbasi, S., Healy, P., Rextin, A.: Improving the running time of embedded upward planarity testing. Inf. Process. Lett. 110(7), 274–278 (2010) MathSciNetCrossRefMATH

Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 6(12), 476–497 (1994) MathSciNetCrossRefMATH

Biedl, T.C., Derka, M.: The (3, 1)-ordering for 4-connected planar triangulations. CoRR abs/1511.00873 (2015)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009) MATH

Di Battista, G., Frati, F.: A survey on small-area planar graph drawing. CoRR abs/1410.1006 (2014)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci. 61(2–3), 175–198 (1988) MathSciNetCrossRefMATH

Di Battista, G., Tamassia, R., Tollis, I.: Area requirement and symmetry display of planar upward drawings. Discrete Comput. Geom. 7(1), 381–401 (1992) MathSciNetCrossRefMATH

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

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

10.

de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: Bipolar orientations revisited. Discrete Appl. Math. 56(2–3), 157–179 (1995). 5th Franco-Japanese Days MathSciNetCrossRefMATH

11.

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 286–297. Springer, Heidelberg (1995). doi: 10.1007/3-540-58950-3_384 CrossRef

12.

Gronemann, M.: Bitonic st-orderings for Upward Planar Graphs. arXiv e-prints, August 2016. http://arxiv.org/abs/1608.08578v1

13.

Gronemann, M.: Bitonic st-orderings of biconnected planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 162–173. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45803-7_14

14.

Gronemann, M.: Algorithms for incremental planar graph drawing and two-page book embeddings. Ph.D. thesis, University of Cologne (2015)

15.

Harel, D., Sardas, M.: An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2), 119–135 (1998) MathSciNetCrossRefMATH

16.

Hutton, M.D., Lubiw, A.: Upward planarity testing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291–311 (1996) MathSciNetCrossRefMATH

17.

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996) MathSciNetCrossRefMATH

18.

Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1), 175–193 (1997) MathSciNetCrossRefMATH

19.

Papakostas, A.: Upward planarity testing of outerplanar dags (extended abstract). In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 298–306. Springer, Heidelberg (1995). doi: 10.1007/3-540-58950-3_385 CrossRef

20.

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

21.

Schmidt, J.M.: The mondshein sequence. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 967–978. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-43948-7_80

Title

Bitonic st-orderings for Upward Planar Graphs

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

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

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_18

Author:

Martin Gronemann

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits