Thickness (graph theory)

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k.[1][2] In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.[3]

Thus, a planar graph has thickness one. Graphs of thickness two are called biplanar graphs. The concept of thickness originates in the Earth–Moon problem on the chromatic number of biplanar graphs, posed in 1959 by Gerhard Ringel,[4] and on a related 1962 conjecture of Frank Harary: Every graph on nine points or its complementary graph is non-planar. The problem is equivalent to determining whether the complete graph K9 is biplanar (it is not, and the conjecture is true).[5] A comprehensive[3] survey on the state of the arts of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal and Mark Scharbrodt.[2]

  1. ^ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math., 66: 567–577, doi:10.1016/S1385-7258(63)50055-9, MR 0157372.
  2. ^ a b Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), "The thickness of graphs: a survey" (PDF), Graphs and Combinatorics, 14 (1): 59–73, CiteSeerX 10.1.1.34.6528, doi:10.1007/PL00007219, MR 1617664, S2CID 31670574.
  3. ^ a b Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009
  4. ^ Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, MR 0109349
  5. ^ Mäkinen, Erkki; Poranen, Timo (2012), "An annotated bibliography on the thickness, outerthickness, and arboricity of a graph", Missouri J. Math. Sci., 24 (1): 76–87, doi:10.35834/mjms/1337950501, S2CID 117703458