nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Hanani-Tutte for Radial Planarity

verfasst von : Radoslav Fulek, Michael Pelsmajer, Marcus Schaefer

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

A drawing of a graph G is radial if the vertices of G are placed on concentric circles \(C_1, \ldots , C_k\) with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling.

We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.

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 Genus, Treewidth, and Local Crossing Number

Nächstes Kapitel Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms and Experiments

The result is stated for x-monotonicity, the special case of level-planarity in which every level contains a single vertex. As we will see below, this special case is equivalent to the general case.

Search for “cylindrical mirror anamorphoses” on the web for many cool pictures of this transformation.

The claim about the invariance of the parity of the winding number of every cycle in Theorem 2 is a consequence of the preservation of the rotation system (a proof will be included in the journal version).

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

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

Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000)MathSciNetCrossRefMATH

Chimani, M., Zeranski, R.: Upward planarity testing: a computational study. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 13–24. Springer, Heidelberg (2013) CrossRef

Chojnacki, C., Hanani, H.: Über wesentlich unplättbare Kurven im dreidimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)

Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035–1046 (1989)CrossRef

Di Giacomo, E., Didimo, W., Liotta, G.: Spine and radial drawings, chapter 8. In: Roberto, T. (ed.) Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, Boca Raton (2013)

Fulek, R., Kynčl, J., Malinović, I., Pálvölgyi, D.: Clustered planarity testing revisited. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 428–439. Springer, Heidelberg (2014)

Fulek, R., Pelsmajer, M., 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)CrossRef

10.

Gross, J.L., Tucker, T.W.: Topological Graph Theory. Dover Publications Inc., Mineola (2001). Reprint of the 1987 originalMATH

11.

Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with Hanani-Tutte for testing \(c\)-planarity. In: McGeoch, C.C., Meyer, U. (eds.) 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 86–97. SIAM, Portland (2014)CrossRef

12.

Jünger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 72–81 (2002)CrossRef

13.

Northway, M.L.: A method for depicting social relationships obtained by sociometric testing. Sociometry 3(2), 144–150 (1940)CrossRef

14.

Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004). Updated version: arXiv:1101.0967 MathSciNetCrossRefMATH

15.

Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani-Tutte on the projective plane. SIAM J. Discrete Math. 23(3), 1317–1323 (2009)MathSciNetCrossRefMATH

16.

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings. J. Combin. Theor. Ser. B 97(4), 489–500 (2007)CrossRefMATH

17.

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings on surfaces. Eur. J. Comb. 30(7), 1704–1717 (2009)CrossRefMATH

18.

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algortihms Appl. 17(4), 367–440 (2013)MathSciNetCrossRefMATH

19.

Schaefer, M.: Hanani-Tutte and related results. In: Bárány, I., Böröczky, K.J., Tóth, G.F., Pach, J. (eds.) A Tribute to László Fejes Tóth. Bolyai Society Mathematical Studies, vol. 24, pp. 259–299. Springer, Berlin (2014)

20.

Tutte, W.T.: Toward a theory of crossing numbers. J. Comb. Theor. 8, 45–53 (1970)MathSciNetCrossRefMATH

21.

Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theor. 32(1), 54–62 (1986)MathSciNetCrossRefMATH

Titel: Hanani-Tutte for Radial Planarity
verfasst von: Radoslav Fulek
Michael Pelsmajer
Marcus Schaefer
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-27261-0_9

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