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 R-3 and that any planar graph admits the same even in R-2. For a graph G and d is an element of{2, 3}, let rho(1)(d) (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.- For d is an element of {2, 3}, we prove that deciding whether rho(1)(d) ( G) = 2. Hence, the problem is not fixed-parameter tractable with respect to k unless P = NP