A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph $G$, the minimum such number (over all drawings in dimension $d in {2,3}$) is called the emph{$d$-dimensional weak line cover number} and denoted by $pi^1_d(G)$. In 3D, the minimum number of emph{planes} needed to cover all vertices of~$G$ is denoted by $pi^2_3(G)$. When edges are also required to be covered, the corresponding numbers $rho^1_d(G)$ and $rho^2_3(G)$ are called the emph{(strong) line cover number} and the emph{(strong) plane cover number}. Computing any of these cover numbers -- except $pi^1_2(G)$ -- is known to be NP-hard. The complexity of computing $pi^1_2(G)$ was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~$G$, whether $pi^1_2(G)=2$. We further show that the universal stacked triangulation of depth~$d$, $G_d$, has $pi^1_2(G_d)=d+1$. Concerning~3D, we show that any $n$-vertex graph~$G$ with $rho^2_3(G)=2$ has at most $5n-19$ edges, which is tight.
Download