Abstract
We study Hanani-Tutte style theorems for various notions of planarity, including partially embedded planarity, and simultaneous planarity. This approach brings together the combinatorial, computational and algebraic aspects of planarity notions and may serve as a uniform foundation for planarity, as suggested in the writings of Tutte and Wu.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 212–225. Springer, Heidelberg (2011)
Angelini, P., Di Battista, G., Frati, F.: Simultaneous Embedding of Embedded Planar Graphs. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 271–280. Springer, Heidelberg (2011)
Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Charikar, M. (ed.) SODA 2010, pp. 202–221. SIAM (2010)
Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, pp. 202–221. SIAM (2010)
Archdeacon, D.: A Kuratowski theorem for the projective plane. J. Graph Theory 5(3), 243–246 (1981)
Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9(1), 53–97 (electronic) (2005)
Bläsius, T., Kobourov, S.G., Rutter, I.: Simutlaneous Embeedings of Planar Graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (to appear)
Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. CoRR abs/1112.0245 (2011)
Bläsius, T., Rutter, I.: Disconnectivity and Relative Positions in Simultaneous Embeddings. ArXiv e-prints (April 2012)
Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. H. Poincaré Sect. B (N.S.) 3, 433–438 (1967)
Chimani, M., Jünger, M., Schulz, M.: Crossing minimization meets simultaneous drawing. In: Visualization Symposium, PacificVIS 2008, pp. 33–40. IEEE (2008)
Chojnacki (Haim Hanani), C.: Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)
Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to VLSI design. In: Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich., 1984), pp. 175–188. Wiley-Intersci. Publ., Wiley, New York (1985)
Cortese, P.F., Di Battista, G.: Clustered planarity. In: Computational Geometry, SCG 2005, pp. 32–34. ACM, New York (2005)
Feng, Q.W.: Algorithms for Drawing Clustered Graphs. Ph.D. thesis, Department of Computer Science and Software engineering, University of Newclastle (April 1997)
Feng, Q.W., Cohen, R.F., Eades, P.: 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., 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 (2012)
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (electronic) (2001)
Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous Graph Embeddings with Fixed Edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 325–335. Springer, Heidelberg (2006)
Glover, H.H., Huneke, J.P., Wang, C.S.: 103 graphs that are irreducible for the projective plane. J. Combin. Theory Ser. B 27(3), 332–370 (1979)
Haeupler, B., Jampani, K.R., Lubiw, A.: Testing Simultaneous Planarity When the Common Graph Is 2-Connected. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol. 6507, pp. 410–421. Springer, Heidelberg (2010)
Haeupler, B., Jampani, K., Lubiw, A.: Testing simultaneous planarity when the common graph is 2-connected. CoRR abs/1009.4517 (2010)
Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. Assoc. Comput. Mach. 21, 549–568 (1974)
Jelínek, V., Kratochvíl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. In: Hurtado, F., van Kreveld, M.J. (eds.) SoCG 2011, pp. 107–116. ACM (2011)
Jünger, M., Leipert, S., Mutzel, P.: Level Planarity Testing in Linear Time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1998)
Kuratowski, C.: Sur les problèmes des courbes gauches en Topologie. Fund. Math. 15, 271–283 (1930)
Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004)
Pach, J., Tóth, G.: Monotone drawings of planar graphs. ArXiv e-prints (January 2011)
Patrignani, M.: On extending a partial straight-line drawing. Internat. J. Found. Comput. Sci. 17(5), 1061–1069 (2006)
Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani–Tutte on the projective plane. SIAM Journal on Discrete Mathematics 23(3), 1317–1323 (2009)
Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing independently even crossings. SIAM Journal on Discrete Mathematics 24(2), 379–393 (2010)
Schaefer, M.: Hanani-Tutte and related results, to appear in Bolyai Memorial Volume
Tamassia, R.: Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. Chapman and Hall (2012) (to appear)
Tutte, W.T.: Toward a theory of crossing numbers. J. Combinatorial Theory 8, 45–53 (1970)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schaefer, M. (2013). Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)