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 R3 and that any planar graph admits the same even in R2. For a graph G and d ∈ {2, 3}, let ρ1d(G) denote the smallest number of lines in Rd whose union contains a crossing-free straight-line drawing of G. For d = 2, the graph G must be planar. Similarly, let ρ23(G) denote the smallest number of planes in R3 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 ∈ {2, 3}, we prove that deciding whether ρ1d(G) ≤ k for a given graph G and integer k is ∃R-complete. • Since NP ⊆ ∃R, deciding ρ1d(G) ≤ k is NP-hard for d ∈ {2, 3}. On the positive side, we show that the problem is fixed-parameter tractable with respect to k. • Since ∃R ⊆ PSPACE, both ρ12(G) and ρ13(G) are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to ρ12 or ρ13 sometimes require irrational coordinates. • We prove that deciding whether ρ23(G) ≤ k is NP-hard for any fixed k ≥ 2. Hence, the problem is not fixed-parameter tractable with respect to k unless P = NP.