The coarseness
of a graph
is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph
. The coarseness of a planar
graph
is therefore .

The coarseness of a graph is the sum of the coarsenesses of its blocks
(Beineke and Chartrand 1968).

The coarseness of the complete graph is known for most values of except , divisible by 3 and greater than or equal to 18, and of the form . For all of these, the values are known to within 1 (Guy
and Beineke 1968; Harary 1994, pp. 121-122).

The coarseness of the complete bipartite graph is known for values of satisfying certain conditions (Beineke and Guy 1969; Harary
1994, pp. 121-122).

Beineke, L. W. and Chartrand, G. "The Coarseness of a Graph." Compos. Math.19, 290-298, 1968.Beineke,
L. W. and Guy, R. K. "The Coarseness of the Complete Bipartite Graph."
Canad. J. Math.21, 1086-1096, 1969.Guy, R. and Beineke,
L. "'THe Coarseness of the Complete Graph." Canad. J. Math.20,
888-894, 1968.Harary, F. "Covering and Packing in Graphs, I."
Ann. New York Acad. Sci.175, 198-205, 1970.Harary, F.
Graph
Theory. Reading, MA: Addison-Wesley, pp. 121-122, 1994.Harary,
F. and Palmer, E. M. Graphical
Enumeration. New York: Academic Press, p. 225, 1973.Harary,
F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In
A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam:
North-Holland, pp. 259-275, 1973.