
arXiv: 1501.00176
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 maximal possible sizes 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.
05C10, 05C42, 05C62, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
05C10, 05C42, 05C62, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
