On properties of maximal 1-planar graphs

Dávid Hudák; Tomáš Madaras; Yusuke Suzuki

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 737-747
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Dávid Hudák, Tomáš Madaras, and Yusuke Suzuki. "On properties of maximal 1-planar graphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 737-747. <http://eudml.org/doc/271067>.

@article{DávidHudák2012,
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.},
author = {Dávid Hudák, Tomáš Madaras, Yusuke Suzuki},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {1-planar graph; maximal graph},
language = {eng},
number = {4},
pages = {737-747},
title = {On properties of maximal 1-planar graphs},
url = {http://eudml.org/doc/271067},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Dávid Hudák
AU - Tomáš Madaras
AU - Yusuke Suzuki
TI - On properties of maximal 1-planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 737
EP - 747
AB - 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.
LA - eng
KW - 1-planar graph; maximal graph
UR - http://eudml.org/doc/271067
ER -

References

top
  1. [1] R. Diestel, Graph Theory (Springer, 2006). 
  2. [2] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250. Zbl0891.05025
  3. [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. Zbl1111.05026
  4. [4] D. Hudák: Štrukt'ura 1-planárnych grafov, Master Thesis, P.J. Šafárik University, Košice, 2009. 
  5. [5] V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319-1327, doi: 10.1016/j.disc.2007.04.009. Zbl1132.05014
  6. [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. Zbl1213.05055
  7. [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. [8] J.W. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math 1 (1963) 163-165, doi: 10.1007/BF02759704. Zbl0119.38806
  9. [9] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427-439, doi: 10.1007/BF01215922. Zbl0902.05017
  10. [10] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107p-117, doi: 10.1007/BF02996313. Zbl0132.20701
  11. [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. Zbl1128.05034
  12. [12] Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010) 1527-1540, doi: 10.1137/090746835. Zbl1221.05099
  13. [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. Zbl0070.18403
  14. [14] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931) 378-?390, doi: 10.2307/1968197. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.