A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1-planar if the addition of any edge violates 1-planarity. Maximal 1-planar graphs have at most An - 8 edges. We show that there are sparse maximal 1-planar graphs with only 45/17n + (O)(1) edges. With a fixed rotation system there are maximal 1-planar graphs with only 7/3n+(O)(1) edges. This is sparser than maximal planar graphs. There cannot be maximal 1-planar graphs with less than 21/10n - (O)(1) edges and less than 28/13n - (O)(1) edges with a fixed rotation system. Furthermore, we prove that a maximal 1-planar rotation system of a graph uniquely determines its 1-planar embedding.
展开▼
