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.
The author gratefully acknowledges support from the Swiss National Science Foundation Grant No. 200021-125287/1 GIG/11/E023.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
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.
- 2.
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.
- 3.
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.
References
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)
Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)
Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000)
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)
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)
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)
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)
Fulek, R., Kynčl, J., Malinović, I., Pálvölgyi, D.: Efficient c-planarity testing algebraically. arXiv:1305.4519
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)
Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. J. CAGD 23, 83–112 (2006)
Guillemin, V., Pollack, A.: Differential Topology. Prentice-Hall (1974)
Hanani, H.: Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundam. Math. 23, 135–142 (1934)
Pach, J., Tóth, G.: Which crossing number is it anyway? J. Combin. Theory Ser. B 80(2), 225–246 (2000)
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)
Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani-Tutte on the projective plane. SIAM J. Discrete Math. 23(3), 1317–1323 (2009)
Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings. J. Combin. Theory Ser. B 97(4), 489–500 (2007)
Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings on surfaces. Eur. J. Comb. 30(7), 1704–1717 (2009)
Schaefer, M.: Hanani-Tutte and related results. Bolyai Memorial Volume (2011)
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)
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)
Tutte, W.T.: Toward a theory of crossing numbers. J. Combin. Theory 8, 45–53 (1970)
Acknowledgment
We would like to express our special thanks of gratitude to the organizers and participants of the 11th GWOP workshop, where we could discuss the research problems treated in the present paper. In particular, we especially benefited from the discussions with Bettina Speckmann, Edgardo Roldán-Pensado and Sebastian Stich. Furthermore, we would like to thank Ján Kynčl for useful discussions at the initial stage, and Gábor Tardos for comments at the final stage of this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fulek, R. (2014). Towards the Hanani-Tutte Theorem for Clustered Graphs. In: Kratsch, D., Todinca, I. (eds) Graph-Theoretic Concepts in Computer Science. WG 2014. Lecture Notes in Computer Science, vol 8747. Springer, Cham. https://doi.org/10.1007/978-3-319-12340-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-12340-0_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12339-4
Online ISBN: 978-3-319-12340-0
eBook Packages: Computer ScienceComputer Science (R0)