It is well known that any graph admits a crossing-free straight-line drawing in R~3 and that any planar graph admits the same even in R~2. For a graph G and d ∈ {2,3}, let ρ_d~1(G) denote the minimum number of lines in 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. 1. For d ∈ {2,3}, we prove that deciding whether ρ_d~1(G) ≤ k for a given graph G and integer k is 3R-complete. 2. Since NP ⊆ ∃R, deciding ρ_d~1(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. 3. Since ∃R ⊆ PSPACE, both ρ_2~1(G) and ρ_3~1(G) are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to ρ_2~1 or ρ_3~1 sometimes require irrational coordinates. 4. Let ρ_3~2(G) be the minimum number of planes in R~3 needed to cover a straight-line drawing of a graph G. We prove that deciding whether ρ_3~2(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.
展开▼
