nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Multilevel Planarity

verfasst von : Lukas Barth, Guido Brückner, Paul Jungeblut, Marcel Radermacher

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

In this paper, we introduce and study the multilevel-planarity testing problem, which is a generalization of upward planarity and level planarity. Let \(G = (V, E)\) be a directed graph and let \(\ell : V \rightarrow \mathcal P(\mathbb Z)\) be a function that assigns a finite set of integers to each vertex. A multilevel-planar drawing of G is a planar drawing of G such that the y-coordinate of each vertex \(v \in V\) is \(y(v) \in \ell (v)\), and each edge is drawn as a strictly y-monotone curve.

We present linear-time algorithms for testing multilevel planarity of embedded graphs with a single source and of oriented cycles. Complementing these algorithmic results, we show that multilevel-planarity testing is NP-complete even in very restricted cases.

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 A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

Nächstes Kapitel Weighted Upper Edge Cover: Complexity and Approximability

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity. In: Hu, Y., Nöllenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 482–495. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50106-2_37CrossRefMATH

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). Theoretical Comput. Sci. 571, 1–9 (2015)MathSciNetCrossRef

Angelini, P., et al.: Testing planarity of partially embedded graphs. ACM Trans. Alg. 11(4), 32:1–32:42 (2015)MathSciNetMATH

Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Alg. Appl. 9(1), 53–97 (2005)MathSciNetCrossRef

Barth, L., Brückner, G., Jungeblut, P., Radermacher, M.: Multilevel planarity (2018). https://arxiv.org/abs/1810.13297

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

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

Brückner, G., Rutter, I.: Partial and constrained level planarity. In: Klein, P.N. (ed.) SODA 2017, pp. 2000–2011 (2017)

De Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187–205 (2012)MathSciNetCrossRef

10.

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs, 1st edn. Prentice Hall PTR (1998)

11.

Di Battista, G., Frati, F.: Efficient C-planarity testing for embedded flat clustered graphs with small faces. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 291–302. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77537-9_29CrossRef

12.

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

13.

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

14.

Garey, M.R., Johnson, D.S.: Two-processor scheduling with start-times and deadlines. SIAM J. Comput. 6(3), 416–426 (1977)MathSciNetCrossRef

15.

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

16.

Harrigan, M., Healy, P.: Practical level planarity testing and layout with embedding constraints. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 62–68. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77537-9_9CrossRefMATH

17.

Jelínek, V., Kratochvíl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. Theory Appl. 46(4), 466–492 (2013)MathSciNetCrossRef

18.

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskočil, T.: Clustered planarity: small clusters in Cycles and Eulerian Graphs. J. Graph Alg. Appl. 13(3), 379–422 (2009)MathSciNetCrossRef

19.

Jünger, M., Leipert, S.: Level planar embedding in linear time. In: Kratochvíyl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 72–81. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46648-7_7CrossRef

20.

Klemz, B., Rote, G.: Ordered level planarity, geodesic planarity and bi-monotonicity. In: Frati, F., Ma, K.-L. (eds.) GD 2017. LNCS, vol. 10692, pp. 440–453. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73915-1_34CrossRefMATH

21.

Leipert, S.: Level planarity testing and embedding in linear time. Ph.D. thesis, University of Cologne (1998)

Titel: Multilevel Planarity
verfasst von: Lukas Barth
Guido Brückner
Paul Jungeblut
Marcel Radermacher
Verlag: Springer International Publishing
Buch: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-10563-1

Electronic ISBN: 978-3-030-10564-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10564-8_18

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"