Line and Plane Cover Numbers Revisited
share
A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph G, the minimum such number (over all drawings in dimension d ∈{2,3}) is called the d-dimensional weak line cover number and denoted by π^1_d(G). In 3D, the minimum number of planes needed to cover all vertices of G is denoted by π^2_3(G). When edges are also required to be covered, the corresponding numbers ρ^1_d(G) and ρ^2_3(G) are called the (strong) line cover number and the (strong) plane cover number. Computing any of these cover numbers – except π^1_2(G)– is known to be NP-hard. The complexity of computing π^1_2(G) was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph G, whether π^1_2(G)=2. We further show that the universal stacked triangulation of depth d, G_d, has π^1_2(G_d)=d+1. Concerning 3D, we show that any n-vertex graph G with ρ^2_3(G)=2 has at most 5n-19 edges, which is tight.
READ FULL TEXT