Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
GraphMaps: Browsing Large Graphs as Interactive Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Hanani-Tutte for Radial Planarity

Authors : Radoslav Fulek, Michael Pelsmajer, Marcus Schaefer

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Log in

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

search-config
loading …

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.

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 Genus, Treewidth, and Local Crossing Number
next chapter Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms and Experiments
Footnotes
1
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.
 
2
Search for “cylindrical mirror anamorphoses” on the web for many cool pictures of this transformation.
 
3
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).
 
Literature
1.
Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9, 2005 (2005)MathSciNetCrossRef
2.
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
3.
4.
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
5.
Chojnacki, C., Hanani, H.: Über wesentlich unplättbare Kurven im dreidimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)
6.
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035–1046 (1989)CrossRef
7.
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)
8.
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)
9.
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.
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.
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.
21.
Metadata
Title
Hanani-Tutte for Radial Planarity
Authors
Radoslav Fulek
Michael Pelsmajer
Marcus Schaefer
Copyright Year
2015
Book
Graph Drawing and Network Visualization

Print ISBN: 978-3-319-27260-3

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

Copyright Year: 2015

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

Premium Partner

    Image Credits