On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs

Július Czap; Jakub Przybyło; Erika Škrabuľáková

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 141-151
  • ISSN: 2083-5892

Abstract

top
A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.

How to cite

top

Július Czap, Jakub Przybyło, and Erika Škrabuľáková. "On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 141-151. <http://eudml.org/doc/276972>.

@article{JúliusCzap2016,
abstract = {A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.},
author = {Július Czap, Jakub Przybyło, Erika Škrabuľáková},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {1-planar graph; bipartite graph; graph size},
language = {eng},
number = {1},
pages = {141-151},
title = {On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs},
url = {http://eudml.org/doc/276972},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Július Czap
AU - Jakub Przybyło
AU - Erika Škrabuľáková
TI - On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 141
EP - 151
AB - A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
LA - eng
KW - 1-planar graph; bipartite graph; graph size
UR - http://eudml.org/doc/276972
ER -

References

top
  1. [1] F.J. Brandenburg, D. Eppstein, A. Gleißner, M.T. Goodrich, K. Hanauer and J. Reislhuber, On the density of maximal 1-planar graphs, Graph Drawing, Lecture Notes Comput. Sci. 7704 (2013) 327–338. doi:10.1007/978-3-642-36763-2_29[Crossref] Zbl06149952
  2. [2] J. Czap and D. Hudák, On drawings and decompositions of 1-planar graphs, Electron. J. Combin. 20 (2013) P54. Zbl1295.05084
  3. [3] J. Czap and D. Hudák, 1-planarity of complete multipartite graphs, Discrete Appl. Math. 160 (2012) 505–512. doi:10.1016/j.dam.2011.11.014[Crossref][WoS] 
  4. [4] R. Diestel, Graph Theory (Springer, New York, 2010). 
  5. [5] 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[Crossref] Zbl1111.05026
  6. [6] D.V. Karpov, An upper bound on the number of edges in an almost planar bipartite graph, J. Math. Sci. 196 (2014) 737–746. doi:10.1007/s10958-014-1690-9[Crossref] Zbl1298.05087
  7. [7] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439. doi:10.1007/BF01215922[Crossref] Zbl0902.05017
  8. [8] H. Bodendiek, R. Schumacher and K. Wagner, Über 1-optimale Graphen, Math. Nachr. 117 (1984) 323–339. doi:10.1002/mana.3211170125[Crossref] Zbl0558.05017
  9. [9] É. Sopena, personal communication, Seventh Cracow Conference in Graph Theory, Rytro (2014). 

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.