AN UPPER BOUND ON THE NUMBER OF EDGES IN AN ALMOST PLANAR BIPARTITE GRAPH

摘要

Let G be a bipartite graph without loops and multiple edges on υ ≥ 4 vertices, which can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that such a graph has at most 3υ - 8 edges for even υ ≠ 6 and at most 3υ - 9 edges for odd υ and for υ = 6. For all υ ≥ 4, examples showing that these bounds are tight are constructed. At the end of the paper, it is discussed a question about drawings of complete bipartite graphs on a plane such that any edge intersects at most one other edge. Bibliography: 6 titles.