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

Improve this question
$\endgroup$
2
  • $\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
    Commented Nov 10, 2018 at 12:16
  • $\begingroup$ Is the question asking about universal sets for 1-plane drawings of planar graphs? $\endgroup$
    – Jan Kyncl
    Commented Jul 10, 2019 at 20:07

0

Reset to default

You must log in to answer this question.