Thickness (graph theory)

From HandWiki

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]Cite error: Closing </ref> missing for <ref> tag and on a related 1962 conjecture of Frank Harary: For any graph on 9 points, either itself 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).[2] 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.[4]

Specific graphs

The thickness of the complete graph on n vertices, Kn, is

[math]\displaystyle{ \left \lfloor \frac{n+7}{6} \right\rfloor, }[/math]

except when n = 9, 10 for which the thickness is three.[5][6]

With some exceptions, the thickness of a complete bipartite graph Ka,b is generally:[7][8]

[math]\displaystyle{ \left \lceil \frac{ab}{2(a+b-2)} \right \rceil. }[/math]

Properties

Every forest is planar, and every planar graph can be partitioned into at most three forests. Therefore, the thickness of any graph G is at most equal to the arboricity of the same graph (the minimum number of forests into which it can be partitioned) and at least equal to the arboricity divided by three.[4][9]

The graphs of maximum degree [math]\displaystyle{ d }[/math] have thickness at most [math]\displaystyle{ \lceil d/2\rceil }[/math].[10] This cannot be improved: for a [math]\displaystyle{ d }[/math]-regular graph with girth at least [math]\displaystyle{ 2d }[/math], the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly [math]\displaystyle{ \lceil d/2\rceil }[/math].[11]

Sulanke's nine-color Earth–Moon map, with adjacencies described by the join of a 6-vertex complete graph and 5-vertex cycle graph (center). Because the adjacencies in this graph are the union of those in two planar maps (left and right) it has thickness two.

Graphs of thickness [math]\displaystyle{ t }[/math] with [math]\displaystyle{ n }[/math] vertices have at most [math]\displaystyle{ t(3n-6) }[/math] edges. Because this gives them average degree less than [math]\displaystyle{ 6t }[/math], their degeneracy is at most [math]\displaystyle{ 6t-1 }[/math] and their chromatic number is at most [math]\displaystyle{ 6t }[/math]. Here, the degeneracy can be defined as the maximum, over subgraphs of the given graph, of the minimum degree within the subgraph. In the other direction, if a graph has degeneracy [math]\displaystyle{ D }[/math] then its arboricity and thickness are at most [math]\displaystyle{ D }[/math]. One can find an ordering of the vertices of the graph in which each vertex has at most [math]\displaystyle{ D }[/math] neighbors that come later than it in the ordering, and assigning these edges to [math]\displaystyle{ D }[/math] distinct subgraphs produces a partition of the graph into [math]\displaystyle{ D }[/math] trees, which are planar graphs.

Even in the case [math]\displaystyle{ t=2 }[/math], the precise value of the chromatic number is unknown; this is Gerhard Ringel's Earth–Moon problem. An example of Thom Sulanke shows that, for [math]\displaystyle{ t=2 }[/math], at least 9 colors are needed.[12]

Related problems

Thickness is closely related to the problem of simultaneous embedding.Cite error: Closing </ref> missing for <ref> tag

Computational complexity

It is NP-hard to compute the thickness of a given graph, and NP-complete to test whether the thickness is at most two.[13] However, the connection to arboricity allows the thickness to be approximated to within an approximation ratio of 3 in polynomial time.

References

  1. ↑ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math. 66: 567–577, doi:10.1016/S1385-7258(63)50055-9 .
  2. ↑ 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, http://projecteuclid.org/euclid.mjms/1337950501 
  3. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named duncan2009
  4. ↑ 4.0 4.1 Cite error: Invalid <ref> tag; no text was provided for refs named mos
  5. ↑ (Mutzel Odenthal), Theorem 3.2.
  6. ↑ Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Mat. Sb., New Series 101 (143): 212–230, doi:10.1070/SM1976v030n02ABEH002267, Bibcode: 1976SbMat..30..187A .
  7. ↑ (Mutzel Odenthal), Theorem 3.4.
  8. ↑ Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), "On the thickness of the complete bipartite graph", Proc. Cambridge Philos. Soc. 60 (1): 1–5, doi:10.1017/s0305004100037385, Bibcode: 1964PCPS...60....1B .
  9. ↑ Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), "On the thickness and arboricity of a graph", Journal of Combinatorial Theory, Series B 52 (1): 147–151, doi:10.1016/0095-8956(91)90100-X .
  10. ↑ Halton, John H. (1991), "On the thickness of graphs of given degree", Information Sciences 54 (3): 219–238, doi:10.1016/0020-0255(91)90052-V 
  11. ↑ Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (2004), "A note on Halton's conjecture", Information Sciences 164 (1–4): 61–64, doi:10.1016/j.ins.2003.06.008 
  12. ↑ "To the Moon and beyond", Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, 2018, pp. 115–133, doi:10.1007/978-3-319-97686-0_11 
  13. ↑ Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society 93 (1): 9–23, doi:10.1017/S030500410006028X, Bibcode: 1983MPCPS..93....9M .



Retrieved from "https://handwiki.org/wiki/index.php?title=Thickness_(graph_theory)&oldid=3358745"