Top

Published in:

2014 | OriginalPaper | Chapter

Towards the Hanani-Tutte Theorem for Clustered Graphs

Author : Radoslav Fulek

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

The weak variant of the Hanani–Tutte theorem says that a graph is planar, if it can be drawn in the plane so that every pair of edges cross an even number of times. Moreover, we can turn such a drawing into an embedding without changing the order in which edges leave the vertices. We prove a generalization of the weak Hanani–Tutte theorem that also easily implies the monotone variant of the weak Hanani–Tutte theorem by Pach and Tóth. Thus, our result can be thought of as a common generalization of these two neat results. In other words, we prove the weak Hanani-Tutte theorem for strip clustered graphs, whose clusters are linearly ordered vertical strips in the plane and edges join only vertices in the same cluster or in neighboring clusters with respect to this order.

Besides usual tools for proving Hanani-Tutte type results our proof combines Hall’s marriage theorem, and a characterization of embedded upward planar digraphs due to Bertolazzi et al.

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 Minimum Spanning Tree Verification Under Uncertainty

next chapter On Set Expansion Problems and the Small Set Expansion Conjecture

This type of clustered graphs is usually called flat clustered graph in the graph drawing literature. We chose this simplified notation in order not to overburden the reader with unnecessary notation.

The argument in the proof of Theorem 3 proves, in fact, a strong variant even in the case, when we require the vertices participating in a cut or two-cut to have the maximum degree three. Hence, we obtained a polynomial time algorithm even in the case of sub-cubic cuts and two-cuts.

We would not have to do anything that follows, if we could turn all the faces into simple ones. However, this seems to be a difficult task.

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 37–48. Springer, Heidelberg (2013)CrossRef

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

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

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. J. Graph Algorithms Appl. 9(3), 391–413 (2005)MathSciNetCrossRefMATH

Cortese, P.F., Di Battista, G.: Clustered planarity (invited lecture). In: Twenty-first Annual Symposium on Computational Geometry (proc. SoCG 05), pp. 30–32. ACM (2005)

Diestel, R.: Graph Theory. Springer, New York (2010)CrossRef

Feng, Q.-W., Cohen, R.F., Eades, R.: How to draw a planar clustered graph. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 21–30. Springer, Heidelberg (1995)CrossRef

Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995)CrossRef

Fulek, R., Kynčl, J., Malinović, I., Pálvölgyi, D.: Efficient c-planarity testing algebraically. arXiv:1305.4519

10.

Fulek, R., Pelsmajer, M., Schaefer, M., Štefankovič, D.: Hanani-Tutte, monotone drawings and level-planarity. In: Pach, J. (ed.) Thirty Essays in Geometric Graph Theory, pp. 263–288. Springer, New York (2012)

11.

Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. J. CAGD 23, 83–112 (2006)MathSciNetMATH

12.

Guillemin, V., Pollack, A.: Differential Topology. Prentice-Hall (1974)

13.

Hanani, H.: Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundam. Math. 23, 135–142 (1934)

14.

Pach, J., Tóth, G.: Which crossing number is it anyway? J. Combin. Theory Ser. B 80(2), 225–246 (2000)MathSciNetCrossRefMATH

15.

Pach, J., Tóth, J.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004). http://arxiv.org/abs/1101.0967(Updated version)MathSciNetCrossRefMATH

16.

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

17.

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

18.

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

19.

Schaefer, M.: Hanani-Tutte and related results. Bolyai Memorial Volume (2011)

20.

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 162–173. Springer, Heidelberg (2013)CrossRef

21.

Schaefer, M., Štefankovič, D.: Block additivity of \(\mathbb{Z}\) \(_\text{2 }\)-embeddings. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 185–195. Springer, Heidelberg (2013)CrossRef

22.

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

Title: Towards the Hanani-Tutte Theorem for Clustered Graphs
Author: Radoslav Fulek
Publisher: Springer International Publishing
Book: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-319-12339-4

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

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-3-319-12340-0_15

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