nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Beyond Level Planarity

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

Erschienen in: Graph Drawing and Network Visualization

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

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.

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

Vorheriges Kapitel Hanani-Tutte for Radial Planarity II

Nächstes Kapitel Track Layout Is Hard

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

Titel: Beyond Level Planarity
verfasst von: Patrizio Angelini
Giordano Da Lozzo
Giuseppe Di Battista
Fabrizio Frati
Maurizio Patrignani
Ignaz Rutter
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

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

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

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"

Premium Partner