Download PDF - On properties of maximal 1-planar graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On properties of maximal 1-planar graphs

Authors 1, 1, 2

Affiliations

  1. Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 041 54 Košice, Slovak Republic
  2. 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

ENG
1-planar graph, maximal graph

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2012/32/4
Export to PBN, Opens in new tab
Pages:
737-747
Main language of publication
English
Received
2011-05-23
Accepted
2012-01-17
Published
2012

DOI: 10.7151/dmgt.1639

Exact and natural sciences