Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants

Schaefer, Marcus (2013) Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , 162-173 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_15).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_15
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
Z Theory > Z.750 Topology
ID Code:1307

Repository Staff Only: item control page

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)