Density of straight-line 1-planar graph drawings

A 1‐planar drawing of a graph is such that each edge is crossed at most once. In 1997, Pach and Tóth showed that any 1‐planar drawing with n vertices has at most $4n-8$ edges and that this bound is tight for $n⩾12$ . We show that, in fact, 1‐planar drawings with n vertices have at most $4n-9$ edges, if we require that the edges are straight‐line segments. We also prove that this bound is tight for infinitely many values of $n⩾8$ . Furthermore, we investigate the density of 1‐planar straight‐line drawings with additional constraints on the vertex positions. We show that 1‐planar drawings of bipartite graphs whose vertices lie on two distinct horizontal layers have at most $1.5n-2$ edges, and we prove that 1‐planar drawings such that all vertices lie on a circumference have at most $2.5n-4$ edges; both these bounds are also tight.