5
$\begingroup$

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).


$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Nov 10 '18 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.