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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1639,
author = {D\'avid Hud\'ak and Tom\'a\v s Madaras and Yusuke Suzuki},
title = {On properties of maximal 1-planar graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {737-747},
zbl = {1293.05065},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1639}
}
Dávid Hudák; Tomáš Madaras; Yusuke Suzuki. On properties of maximal 1-planar graphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 737-747. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1639/
[000] [1] R. Diestel, Graph Theory (Springer, 2006).
[001] [2] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250. | Zbl 0891.05025
[002] [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. | Zbl 1111.05026
[003] [4] D. Hudák: Štrukt'ura 1-planárnych grafov, Master Thesis, P.J. Šafárik University, Košice, 2009.
[004] [5] V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319-1327, doi: 10.1016/j.disc.2007.04.009. | Zbl 1132.05014
[005] [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. | Zbl 1213.05055
[006] [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
[007] [8] J.W. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math 1 (1963) 163-165, doi: 10.1007/BF02759704. | Zbl 0119.38806
[008] [9] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427-439, doi: 10.1007/BF01215922. | Zbl 0902.05017
[009] [10] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107p-117, doi: 10.1007/BF02996313. | Zbl 0132.20701
[010] [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. | Zbl 1128.05034
[011] [12] Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010) 1527-1540, doi: 10.1137/090746835. | Zbl 1221.05099
[012] [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. | Zbl 0070.18403
[013] [14] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931) 378-?390, doi: 10.2307/1968197.