Geodesic
On properties of maximal 1-planar graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 737-747.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2012_32_4_a9,
     author = {Hud\'ak, D\'avid and Madaras, Tom\'a\v{s} and Suzuki, Yusuke},
     title = {On properties of maximal 1-planar graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {737--747},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a9/}
}
TY  - JOUR
AU  - Hudák, Dávid
AU  - Madaras, Tomáš
AU  - Suzuki, Yusuke
TI  - On properties of maximal 1-planar graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 737
EP  - 747
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a9/
LA  - en
ID  - DMGT_2012_32_4_a9
ER  - 
%0 Journal Article
%A Hudák, Dávid
%A Madaras, Tomáš
%A Suzuki, Yusuke
%T On properties of maximal 1-planar graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 737-747
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a9/
%G en
%F DMGT_2012_32_4_a9
Hudák, Dávid; Madaras, Tomáš; Suzuki, Yusuke. On properties of maximal 1-planar graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 737-747. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a9/

[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:2170::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.