## On Properties of Maximal 1-planar Graphs

 Dávid Hudák, Tomáš Madaras Institute of Mathematics, Faculty of Sciences University of P. J. Šafárik Jesenná 5, 041 54 Košice, Slovak Republic Yusuke Suzuki Department of Mathematics, Faculty of Science Niigata University 8050, Ikarashi 2-no-cho, Nishi-ku, Niigata, 950-2181, Japan

## Abstract

A graph is called 1-planar if there exists a drawing in the plane so that each edge contains at most one crossing. We study maximal 1-planar graphs from the point of view of properties of their diagrams, local structure and hamiltonicity.

Keywords: 1-planar graph, maximal graph

2010 Mathematics Subject Classification: 05C10.

## References

 [1] R. Diestel, Graph Theory (Springer, 2006). [2] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245--250. [3] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007) 854--865, doi: 10.1016/j.disc.2005.11.056. [4] D. Hudák: Štrukt'ura 1-planárnych grafov, Master Thesis, P.J. Šafárik University, Košice, 2009. [5] V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319--1327, doi: 10.1016/j.disc.2007.04.009. [6] V. P. Korzhik and B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, Springer Lecture Notes in Computer Science 5417 (2009) 302--312, doi: 10.1007/978-3-642-00219-9_29. [7] B. Mohar, Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34 (2000) 170--179, doi: 10.1002/1097-0118(200006)34:2<170::AID-JGT6>3.0.CO;2-P. [8] J.W. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math 1 (1963) 163--165, doi: 10.1007/BF02759704. [9] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427--439, doi: 10.1007/BF01215922. [10] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107p--117, doi: 10.1007/BF02996313. [11] T. Kaiser, D. Král, M. Rosenfeld, Z. Ryjáček and H.-J. Voss: Hamilton cycles in prisms over graphs, http://cam.zcu.cz/∼ryjacek/publications/files/60.pdf. [12] Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010) 1527--1540, doi: 10.1137/090746835. [13] W. T. Tutte, A theorem on planar graphs, Trans. Am. Math. Soc. 82 (1956) 99--116, doi: 10.1090/S0002-9947-1956-0081471-8. [14] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931) 378-?390, doi: 10.2307/1968197.