The coarseness ξ(G) of a graph G is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph G. The coarseness of a planar graph G is therefore ξ(G) = 0. The coarseness of a graph is the sum of the coarsenesses of its blocks. The coarseness of the complete graph K_n is known for most values of n except n = 13, n divisible by 3 and greater than or equal to 18, and n of the form 9k + 7. For all of these, the values are known to within 1 (Guy and Beineke 1968; Harary 1994, pp. 121-122).

graph thickness | nonplanar graph