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 }_d^1(G)$ denote the smallest number of lines in ${\mathbb{R}}^d$ whose union contains a crossing-free straight-line drawing of $G$. For $d=2$, $G$ must be planar. Similarly, let ${\rho }_3^2(G)$ denote the smallest number of planes in ${\mathbb{R}}^3$ whose union contains a crossing-free straight-line drawing of $G$. We investigate the complexity of computing these three parameters and obtain the following hardness and algorithmic results.

• For $d\in \{2,3\}$, we prove that deciding whether ${\rho }_d^1(G)\le k$ for a given graph $G$ and integer $k$ is $\mathrm{\exists }\mathbb{R}$-complete.
• Since $\mathrm{N}\mathrm{P}\subseteq \mathrm{\exists }\mathbb{R}$, deciding $\rho^1_d(G)\le k$isNP-hardfor$d\in{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$.
• Since $\mathrm{\exists }\mathbb{R}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, both ${\rho }_2^1(G)$ and ${\rho }_3^1(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to ${\rho }_2^1$ or ${\rho }_3^1$ sometimes require irrational coordinates.
• We prove that deciding whether ${\rho }_3^2(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{N}\mathrm{P}$.