# Universal point sets for 1-plane graphs

It is a notorious open problem to find a smallest set of $$N$$ points that permit any $$n$$-vertex planar graph to be drawn in the plane without crossings, using only those $$N$$ points as vertices, and straight segments as edges. An upperbound of $$O(n^2)$$ is provided by integer grids, but the best lowerbound is linear in $$n$$. A point set that allows such plane drawings for every $$n$$-vertex planar graph is called a universal set.

My question is:

Q. Are there subquadratic universal sets for drawing $$1$$-plane graphs, graphs that have a straight-line drawing where each edge is crossed by at most one other edge? If this is not known, are there subquadratic universal sets for drawing $$k$$-plane graphs, for some $$k > 1$$?

As $$k$$ approaches $$n$$, there should be linear-size universal sets.

Fig.1: Chaplick, Steven, Fabian Lipp, Alexander Wolff, and Johannes Zink.
"Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends." arXiv:1806.10044 (2018).

• 1-planar graphs have a drawing---not necessarily with straight edges---where each edge is crossed by at most one other edge. I'm using "1-plane graphs" to also require straight edges. – Joseph O'Rourke Nov 10 '18 at 12:16