PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 4 | 737-747
Tytuł artykułu

On properties of maximal 1-planar graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
32
Numer
4
Strony
737-747
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-05-23
poprawiono
2012-01-17
zaakceptowano
2012-01-18
Twórcy
  • Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 041 54 Košice, Slovak Republic
  • Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 041 54 Košice, Slovak Republic
  • Department of Mathematics, Faculty of Science, Niigata University, 8050, Ikarashi 2-no-cho, Nishi-ku, Niigata, 950-2181, Japan
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1639
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.