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 v ≥ 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 v - 8 edges for even v ≠ 6 and at most 3 v - 9 edges for odd v and for v = 6. For all v ≥ 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. [ABSTRACT FROM AUTHOR]