PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 141-151
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
36
Numer
1
Strony
141-151
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2015-02-28
poprawiono
2015-05-27
zaakceptowano
2015-05-27
online
2016-01-19
Twórcy
autor
  • Department of Applied Mathematics and Business Informatics Faculty of Economics Technical University of Košice, Němcovej 32, 040 01 Košice, Slovakia, julius.czap@tuke.sk
  • AGH University of Science and Technology Faculty of Applied Mathematics al. A. Mickiewicza 30, 30–059 Kraków, Poland, jakubprz@agh.edu.pl
  • Institute of Control and Informatization of Production Processes Faculty of Mining, Ecology, Process Control and Geotechnology, Technical University of Košice, Košice, Slovakia, erika.skrabulakova@tuke.sk
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1845
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ć.