The Complexity of Drawing Graphs on Few Lines and Few Planes

It is well known that any graph admits a crossing-free straight-line drawing in $mathbb{R}^3$ and that any planar graph admits the same even in $mathbb{R}^2$. For a graph $G$ and $d in {2,3}$, let $rho^1_d(G)$ denote the minimum number of lines in $mathbb{R}^d$ that together can cover all edges of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. - For $din{2,3}$, we prove that deciding whether $rho^1_d(G)le k$ for a given graph $G$ and integer $k$ is ${existsmathbb{R}}$-complete. - Since $mathrm{NP}subseteq{existsmathbb{R}}$, deciding $rho^1_d(G)le k$ is NP-hard for $din{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${existsmathbb{R}}subseteqmathrm{PSPACE}$, both $rho^1_2(G)$ and $rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $rho^1_2$ or $rho^1_3$ sometimes require irrational coordinates. - Let $rho^2_3(G)$ be the minimum number of planes in $mathbb{R}^3$ needed to cover a straight-line drawing of a graph $G$. We prove that deciding whether $rho^2_3(G)le k$ is NP-hard for any fixed $k ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $mathrm{P}=mathrm{NP}$.