Thickness (graph theory): Difference between revisions

Content deleted Content added

Inline

Revision as of 00:49, 7 January 2023

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 1. Graphs of thickness 2 are called biplanar graphs. The concept of thickness originates in the 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 $K 9$ is biplanar (it is not, and the conjecture is true).^[4] 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]

Specific graphs

The thickness of the complete graph on $n$ vertices, $K n$ , is

\left\lfloor {\frac {n+7}{6}}\right\rfloor ,

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

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

\left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .

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.^[2]^[9]

Graphs of thickness $t$ with $n$ vertices have at most $t(3n-6)$ edges. Because this gives them average degree less than $6t$ , their degeneracy is at most $6t-1$ and their chromatic number is at most $6t$ . 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 $D$ then its arboricity and thickness are at most $D$ . One can find an ordering of the vertices of the graph in which each vertex has at most $D$ neighbors that come later than it in the ordering, and assigning these edges to $D$ distinct subgraphs produces a partition of the graph into $D$ trees, which are planar graphs.

Even in the case $\theta =2$ , 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 $\theta =2$ , at least 9 colors are needed.^[10]

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

^ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math., 66: 567–577, doi:10.1016/S1385-7258(63)50055-9, MR 0157372.
^ ^a ^b ^c 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.
^ ^a ^b Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009
^ 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
^ Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.2.
^ Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Mat. Sb., New Series, 101 (143): 212–230, Bibcode:1976SbMat..30..187A, doi:10.1070/SM1976v030n02ABEH002267, MR 0460162.
^ Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.4.
^ 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, Bibcode:1964PCPS...60....1B, doi:10.1017/s0305004100037385, MR 0158388, S2CID 122829092.
^ 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, MR 1109429.
^ Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641
^ Brass, Peter; Cenek, Eowyn; Duncan, Cristian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007), "On simultaneous planar graph embeddings", Computational Geometry, 36 (2): 117–130, doi:10.1016/j.comgeo.2006.05.006, MR 2278011.
^ Eppstein, David (2004), "Separating thickness from geometric thickness", Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, pp. 75–86, arXiv:math/0204252, doi:10.1090/conm/342/06132, MR 2065254.
^ Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23, Bibcode:1983MPCPS..93....9M, doi:10.1017/S030500410006028X, MR 0684270, S2CID 122028023.

[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.

[mos-2] 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.

[duncan2009-3] Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009

[anno-4] 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

[5] Mutzel, Odenthal & Scharbrodt (1998), 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, Bibcode:1976SbMat..30..187A, doi:10.1070/SM1976v030n02ABEH002267, MR 0460162.

[7] Mutzel, Odenthal & Scharbrodt (1998), 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, Bibcode:1964PCPS...60....1B, doi:10.1017/s0305004100037385, MR 0158388, S2CID 122829092.

[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, MR 1109429.

[10] Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641

[11] Brass, Peter; Cenek, Eowyn; Duncan, Cristian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007), "On simultaneous planar graph embeddings", Computational Geometry, 36 (2): 117–130, doi:10.1016/j.comgeo.2006.05.006, MR 2278011.

[12] Eppstein, David (2004), "Separating thickness from geometric thickness", Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, pp. 75–86, arXiv:math/0204252, doi:10.1090/conm/342/06132, MR 2065254.

[13] Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23, Bibcode:1983MPCPS..93....9M, doi:10.1017/S030500410006028X, MR 0684270, S2CID 122028023.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 16: / Line 16: @@
 :<math>\left \lceil \frac{ab}{2(a+b-2)} \right \rceil.</math>
+==Properties==
-==Related problems==
-Every [[Tree (graph theory)|forest]] is planar, and every planar graph can be partitioned into at most three forests. Therefore, the thickness of any graph {{mvar|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.<ref name="mos"/><ref>{{citation | last1 = Dean | first1 = Alice M. | last2 = Hutchinson | first2 = Joan P. | author2-link = Joan Hutchinson | last3 = Scheinerman | first3 = Edward R. | author3-link = Ed Scheinerman | doi = 10.1016/0095-8956(91)90100-X | issue = 1 | journal = [[Journal of Combinatorial Theory]] | mr = 1109429 | pages = 147–151 | series = Series B | title = On the thickness and arboricity of a graph | volume = 52 | year = 1991| doi-access = free }}.</ref> The thickness of {{mvar|G}} is also within constant factors of another standard [[graph invariant]], the [[degeneracy (graph theory)|degeneracy]], defined as the maximum, over subgraphs of {{mvar|G}}, of the minimum degree within the subgraph. If an {{mvar|n}}-vertex graph has thickness ''t'' then it necessarily has at most {{math|''t''(3''n'' − 6)}} edges, from which it follows that its degeneracy is at most {{math|6''t'' − 1}}. In the other direction, if a graph has degeneracy {{mvar|D}} then it has arboricity, and thickness, at most {{mvar|D}}.
+Every [[Tree (graph theory)|forest]] is planar, and every planar graph can be partitioned into at most three forests. Therefore, the thickness of any graph {{mvar|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.<ref name="mos"/><ref>{{citation | last1 = Dean | first1 = Alice M. | last2 = Hutchinson | first2 = Joan P. | author2-link = Joan Hutchinson | last3 = Scheinerman | first3 = Edward R. | author3-link = Ed Scheinerman | doi = 10.1016/0095-8956(91)90100-X | issue = 1 | journal = [[Journal of Combinatorial Theory]] | mr = 1109429 | pages = 147–151 | series = Series B | title = On the thickness and arboricity of a graph | volume = 52 | year = 1991| doi-access = free }}.</ref>
+[[File:Sulanke Earth-Moon map.svg|thumb|upright=1.8|Sulanke's nine-color Earth–Moon map, with adjacencies described by the [[Graph operations|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>t</math> with <math>n</math> vertices have at most <math>t(3n-6)</math> edges. Because this gives them average degree less than <math>6t</math>, their [[Degeneracy (graph theory)|degeneracy]] is at most <math>6t-1</math> and their [[chromatic number]] is at most <math>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>D</math> then its arboricity and thickness are at most <math>D</math>. One can find an ordering of the vertices of the graph in which each vertex has at most <math>D</math> neighbors that come later than it in the ordering, and assigning these edges to <math>D</math> distinct subgraphs produces a partition of the graph into <math>D</math> trees, which are planar graphs.
+Even in the case <math>\theta=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>\theta=2</math>, at least 9 colors are needed.<ref>{{citation
+ | last = Gethner | first = Ellen | author-link = Ellen Gethner
+ | editor1-last = Gera | editor1-first = Ralucca | editor1-link = Ralucca Gera
+ | editor2-last = Haynes | editor2-first = Teresa W. | editor2-link = Teresa W. Haynes
+ | editor3-last = Hedetniemi | editor3-first = Stephen T.
+ | contribution = To the Moon and beyond
+ | doi = 10.1007/978-3-319-97686-0_11
+ | mr = 3930641
+ | pages = 115–133
+ | publisher = Springer International Publishing
+ | series = Problem Books in Mathematics
+ | title = Graph Theory: Favorite Conjectures and Open Problems, II
+ | year = 2018}}</ref>
+==Related problems==
 Thickness is closely related to the problem of [[simultaneous embedding]].<ref>{{citation| last1 = Brass | first1 = Peter
 | last2 = Cenek | first2 = Eowyn | last3 = Duncan | first3 = Cristian A. | last4 = Efrat | first4 = Alon | last5 = Erten | first5 = Cesim | last6 = Ismailescu | first6 = Dan P. | last7 = Kobourov | first7 = Stephen G. | last8 = Lubiw | first8 = Anna | author8-link = Anna Lubiw | last9 = Mitchell | first9 = Joseph S. B. | author9-link = Joseph S. B. Mitchell  | doi = 10.1016/j.comgeo.2006.05.006 | issue = 2 | journal = Computational Geometry | mr = 2278011 | pages = 117–130 | title = On simultaneous planar graph embeddings | volume = 36 | year = 2007| doi-access = free }}.</ref> If two or more planar graphs all share the same vertex set, then it is possible to embed all these graphs in the plane, with the edges drawn as curves, so that each vertex has the same position in all the different drawings. However, it may not be possible to construct such a drawing while keeping the edges drawn as straight [[line segment]]s.