Top

Published in:

2016 | OriginalPaper | Chapter

Hanani-Tutte for Radial Planarity II

Authors : Radoslav Fulek, Michael Pelsmajer, Marcus Schaefer

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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. A pair of edges e and f in a graph is independent if e and f do not share a vertex.

We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane

next chapter Beyond Level Planarity

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

Note that we define an essential curve slightly differently than usual.

Angelini, P., Lozzo, G., Battista, G., Frati, F.: Strip planarity testing. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 37–48. Springer, Heidelberg (2013). doi:10.1007/978-3-319-03841-4_4 CrossRef

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity. arXiv preprint arXiv:1510.08274 (2015)

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

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

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), 16 (2016)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)MathSciNetCrossRefMATH

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

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

Di Giacomo, E., Didimo, W., Liotta, G.: Spine and radial drawings, Chap. 8, pp. 247–284. Discrete Mathematics and Its Applications. Chapman and Hall/CRC (2013)

10.

Feng, Q.-W., Cohen, R.F., Eades, P.: How to draw a planar clustered graph. In: Ding-Zhu, D., Li, M. (eds.) Computing and Combinatorics. LNCS, vol. 959, pp. 21–30. Springer, Berlin Heidelberg (1995)CrossRef

11.

Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995). doi:10.1007/3-540-60313-1_145

12.

Fulek, R.: Towards the Hanani-Tutte theorem for clustered graphs. In: Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, 25–27 June 2014. Revised Selected Papers, pp. 176–188 (2014). arXiv:1410.3022v2

13.

Fulek, R.: Bounded embeddings of graphs in the plane. In: Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, 17–19 August 2016, Proceedings, pp. 31–42 (2016)

14.

Fulek, R., Kynčl, J., Malinovic, I., Pálvölgyi, D.: Clustered planarity testing revisited. Electron. J. Combinatorics 22 (2015)

15.

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

16.

Fulek, R., Pelsmajer, M.J., Schaefer, M.: Hanani-Tutte for radial planarity. In: Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, 24–26 September 2015, Revised Selected Papers, pp. 99–110 (2015)

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

Skopenkov, M.: On approximability by embeddings of cycles in the plane. Topology Appl. 134(1), 1–22 (2003)MathSciNetCrossRefMATH

24.

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

Title: Hanani-Tutte for Radial Planarity II
Authors: Radoslav Fulek
Michael Pelsmajer
Marcus Schaefer
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner