graph depth

The thickness (or depth) t(G) or θ(G) of a graph G is the minimum number of planar edge-induced subgraphs P_i of F needed such that the graph union union _i P_i = G. The thickness of a planar graph G is therefore t(G) = 1, and the thickness of a nonplanar graph G satisfies t(G)>=2. A graph which is the union of two planar graph (i.e., that has thickness 1 or 2) is said to be a biplanar graph. Determining the thickness of a graph is an NP-complete problem. Precomputed thicknesses for many small named or indexed graphs can be obtained in the Wolfram Language using GraphData[graph, Thickness].

biplanar graph | graph coarseness | planar graph