# David Eppstein - Publications

##
Publications with Josef Reislhuber

**On the density of maximal 1-planar graphs**.

F. J. Brandenburg,
D. Eppstein,
A. Gleißner,
M. T. Goodrich,
K. Hanauer, and
J. Reislhuber.

*20th Int. Symp. Graph Drawing*, Redmond, Washington, 2012.

Springer, *Lecture Notes in Comp. Sci.* 7704, 2013, pp. 327–338.

A graph is 1-planar if it can be drawn in the plane with at most one
crossing per edge, and maximal 1-planar if it is 1-planar but adding any
edge would force more than one crossing on some edge or edges. Although
maximal 1-planar graphs on *n* vertices may have as many as
4*n* − 8 edges, we show that there exist maximal
1-planar graphs with as few as 45*n*/17 + O(1) edges.

Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.