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

• Autorzy: Július Czap , Jakub Przybyło , Erika Škrabuľáková
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

1-planar graph; bipartite graph; graph size

Kategorie tematyczne

• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C42: Density (toughness, etc.)
• 05C10: Planar graphs; geometric and topological aspects of graph theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 141-151

Daty

wydano

2016-02-01

otrzymano

2015-02-28

poprawiono

2015-05-27

zaakceptowano

2015-05-27

online

2016-01-19

Twórcy

autor

Július Czap

• Department of Applied Mathematics and Business Informatics Faculty of Economics Technical University of Košice, Němcovej 32, 040 01 Košice, Slovakia

autor

Jakub Przybyło

• AGH University of Science and Technology Faculty of Applied Mathematics al. A. Mickiewicza 30, 30–059 Kraków, Poland

autor

Erika Škrabuľáková

• Institute of Control and Informatization of Production Processes Faculty of Mining, Ecology, Process Control and Geotechnology, Technical University of Košice, Košice, Slovakia

Bibliografia

• [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]
• [2] J. Czap and D. Hudák, On drawings and decompositions of 1-planar graphs, Electron. J. Combin. 20 (2013) P54.
• [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] R. Diestel, Graph Theory (Springer, New York, 2010).
• [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]
• [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]
• [7] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439. doi:10.1007/BF01215922[Crossref]
• [8] H. Bodendiek, R. Schumacher and K. Wagner, Über 1-optimale Graphen, Math. Nachr. 117 (1984) 323–339. doi:10.1002/mana.3211170125[Crossref]
• [9] É. Sopena, personal communication, Seventh Cracow Conference in Graph Theory, Rytro (2014).

Identyfikatory

DOI

10.7151/dmgt.1845