Top

previous chapter Hanani-Tutte for Radial Planarity II

next chapter Track Layout Is Hard

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Beyond Level Planarity

Read first chapter

Authors: Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity, are polynomial-time solvable.

Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels.

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

We consider connected orientable surfaces; the genus of a surface is the maximum number of cuttings along non-intersecting closed curves that do not disconnect it.

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity. CoRR abs/1510.08274v3 (2015). http://arxiv.org/abs/1510.08274v3

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper: (in clustered-level planarity and T-level planarity). Theor. Comput. Sci. 571, 1–9 (2015). http://dx.doi.org/10.1016/j.tcs.2014.12.019 MathSciNetCrossRefMATH

Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A.: Classification of planar upward embedding. In: Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 415–426. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-25878-7_39 CrossRef

Bachmaier, C., Brandenburg, F., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9(1), 53–97 (2005). http://jgaa.info/accepted/2005/BachmaierBrandenburgForster2005.9.1.pdf MathSciNetCrossRefMATH

Bachmaier, C., Brunner, W.: Linear time planarity testing and embedding of strongly connected cyclic level graphs. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 136–147. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-87744-8_12 CrossRef

Bachmaier, C., Brunner, W., König, C.: Cyclic level planarity testing and embedding. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 50–61. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-77537-9_8 CrossRef

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embeddings of planar graphs (Chap. 11). In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications, pp. 349–382. Chapman and Hall/CRC, Boca Raton (2013)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), 16 (2016). http://doi.acm.org/10.1145/2738054 MathSciNet

Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976). http://dx.doi.org/10.1016/S0022-0000(76)80045–1 MathSciNetCrossRefMATH

10.

Brandenburg, F.: Upward planar drawings on the standing and the rolling cylinders. Comput. Geom. 47(1), 25–41 (2014). http://dx.doi.org/10.1016/j.comgeo.2013.08.003 MathSciNetCrossRefMATH

11.

Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom. 36(2), 117–130 (2007). http://dx.doi.org/10.1016/j.comgeo.2006.05.006 MathSciNetCrossRefMATH

12.

Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035–1046 (1988). http://dx.doi.org/10.1109/21.23105 MathSciNetCrossRefMATH

13.

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: On the characterization of level planar trees by minimal patterns. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 69–80. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-11805-0_9 CrossRef

14.

Forster, M., Bachmaier, C.: Clustered level planarity. In: Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 218–228. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-24618-3_18 CrossRef

15.

Fulek, R., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings, and level-planarity. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 263–287. Springer, New York (2013). http://dx.doi.org/10.1007/978-1-4614-0110-0_14 CrossRef

16.

Haeupler, B., Raju Jampani, K., Lubiw, A.: Testing simultaneous planarity when the common graph is 2-connected. J. Graph Algorithms Appl. 17(3), 147–171 (2013). http://dx.doi.org/10.7155/jgaa.00289 MathSciNetCrossRefMATH

17.

Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Math. 280(1–3), 51–63 (2004). http://dx.doi.org/10.1016/j.disc.2003.02.001 MathSciNetCrossRefMATH

18.

Heath, L.S., Pemmaraju, S.V.: Recognizing leveled-planar dags in linear time. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 300–311. Springer, Heidelberg (1996). doi: 10.1007/BFb0021813 CrossRef

19.

Hsu, W., McConnell, R.M.: PQ trees, PC trees, and planar graphs. In: Mehta, D.P., Sahni, S. (eds.) Handbook of Data Structures and Applications. Chapman and Hall/CRC, Boca Raton (2004). http://dx.doi.org/10.1201/9781420035179

20.

Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1998). doi: 10.1007/3-540-37623-2_17 CrossRef

21.

Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111–114 (1979) MathSciNetCrossRefMATH

22.

Randerath, B., Speckenmeyer, E., Boros, E., Hammer, P.L., Kogan, A., Makino, K., Simeone, B., Cepek, O.: A satisfiability formulation of problems on level graphs. Electron. Notes Discrete Math. 9, 269–277 (2001). http://dx.doi.org/10.1016/S1571-0653(04)00327–0 CrossRefMATH

23.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109–125 (1981). http://dx.doi.org/10.1109/TSMC.1981.4308636 MathSciNetCrossRef

24.

Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized k-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation. Discrete Appl. Math. 160(16–17), 2349–2363 (2012). http://dx.doi.org/10.1016/j.dam.2012.05.028 MathSciNetCrossRefMATH

Title

Beyond Level Planarity

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_37

Authors:

Patrizio Angelini
Giordano Da Lozzo
Giuseppe Di Battista
Fabrizio Frati
Maurizio Patrignani
Ignaz Rutter

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits