Thickness (graph theory)

<h2 id="specific-graphs">Specific graphs</h2>
The thickness of the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on n vertices, Kn, is

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

except when n = 9, 10 for which the thickness is three.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
With some exceptions, the thickness of a <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> Ka,b is generally:<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

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

<h2 id="properties">Properties</h2>
Every <a href="/facts/Tree_(graph_theory)/TCWk4Joy">forest</a> 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 <a href="/facts/Arboricity/JjfuCv8r">arboricity</a> 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
The graphs of maximum degree 
 
 
 
 d
 
 
 {\displaystyle d}
 
 have thickness at most 
 
 
 
 ⌈
 d
 
 /
 
 2
 ⌉
 
 
 {\displaystyle \lceil d/2\rceil }
 
.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> This cannot be improved: for a 
 
 
 
 d
 
 
 {\displaystyle d}
 
-regular graph with <a href="/facts/Girth_(graph_theory)/rPwRGgxj">girth</a> at least 
 
 
 
 2
 d
 
 
 {\displaystyle 2d}
 
, the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly 
 
 
 
 ⌈
 d
 
 /
 
 2
 ⌉
 
 
 {\displaystyle \lceil d/2\rceil }
 
.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

Graphs of thickness 
 
 
 
 t
 
 
 {\displaystyle t}
 
 with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices have at most 
 
 
 
 t
 (
 3
 n
 −
 6
 )
 
 
 {\displaystyle t(3n-6)}
 
 edges. Because this gives them average degree less than 
 
 
 
 6
 t
 
 
 {\displaystyle 6t}
 
, their <a href="/facts/Degeneracy_(graph_theory)/IaYkus22">degeneracy</a> is at most 
 
 
 
 6
 t
 −
 1
 
 
 {\displaystyle 6t-1}
 
 and their <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> is at most 
 
 
 
 6
 t
 
 
 {\displaystyle 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
 
 
 {\displaystyle D}
 
 then its arboricity and thickness are at most 
 
 
 
 D
 
 
 {\displaystyle D}
 
. One can find an ordering of the vertices of the graph in which each vertex has at most 
 
 
 
 D
 
 
 {\displaystyle D}
 
 neighbors that come later than it in the ordering, and assigning these edges to 
 
 
 
 D
 
 
 {\displaystyle D}
 
 distinct subgraphs produces a partition of the graph into 
 
 
 
 D
 
 
 {\displaystyle D}
 
 trees, which are planar graphs.
Even in the case 
 
 
 
 t
 =
 2
 
 
 {\displaystyle t=2}
 
, the precise value of the chromatic number is unknown; this is <a href="/facts/Gerhard_Ringel/7Wxupm0s">Gerhard Ringel</a>'s <a href="/facts/Earth%25E2%2580%2593Moon_problem/enLuc2NJ">Earth–Moon problem</a>. An example of Thom Sulanke shows that, for 
 
 
 
 t
 =
 2
 
 
 {\displaystyle t=2}
 
, at least 9 colors are needed.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h2 id="related-problems">Related problems</h2>
Thickness is closely related to the problem of <a href="/facts/Simultaneous_embedding/Ncdd2U0C">simultaneous embedding</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> 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 <a href="/facts/Line_segment/V8E0M4qk">line segments</a>.
A different graph invariant, the rectilinear thickness or geometric thickness of a graph G, counts the smallest number of planar graphs into which G can be decomposed subject to the restriction that all of these graphs can be drawn simultaneously with straight edges. The <a href="/facts/Book_embedding/2hz3yIP7">book thickness</a> adds an additional restriction, that all of the vertices be drawn in <a href="/facts/Convex_position/lzW3leK9">convex position</a>, forming a <a href="/facts/Circular_layout/41o5E5my">circular layout</a> of the graph. However, in contrast to the situation for arboricity and degeneracy, no two of these three thickness parameters are always within a constant factor of each other.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<h2 id="computational-complexity">Computational complexity</h2>
It is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> to compute the thickness of a given graph, and <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> to test whether the thickness is at most two.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> However, the connection to arboricity allows the thickness to be approximated to within an <a href="/facts/Approximation_ratio/BWlf7M32">approximation ratio</a> of 3 in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.

<h2 id="references">References</h2>

<ol>
<li id="fn: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. <a href="/wiki/W._T._Tutte" target="_blank">/wiki/W._T._Tutte</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Petra_Mutzel" target="_blank">/wiki/Petra_Mutzel</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009 <a href="https://cccg.ca/proceedings/2009/cccg09_04.pdf" target="_blank">https://cccg.ca/proceedings/2009/cccg09_04.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, MR 0109349 <a href="/wiki/Gerhard_Ringel" target="_blank">/wiki/Gerhard_Ringel</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="https://projecteuclid.org/euclid.mjms/1337950501" target="_blank">https://projecteuclid.org/euclid.mjms/1337950501</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009 <a href="https://cccg.ca/proceedings/2009/cccg09_04.pdf" target="_blank">https://cccg.ca/proceedings/2009/cccg09_04.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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 href="/wiki/Petra_Mutzel" target="_blank">/wiki/Petra_Mutzel</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.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 <a href="https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/9097519627562713c125630a0047835e/$FILE/MPI-I-96-1-009.pdf" target="_blank">https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/9097519627562713c125630a0047835e/$FILE/MPI-I-96-1-009.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">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. <a href="/wiki/Matematicheskii_Sbornik" target="_blank">/wiki/Matematicheskii_Sbornik</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.4. - 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 href="https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/9097519627562713c125630a0047835e/$FILE/MPI-I-96-1-009.pdf" target="_blank">https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/9097519627562713c125630a0047835e/$FILE/MPI-I-96-1-009.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), "On the thickness of the complete bipartite graph", Mathematical Proceedings of the Cambridge Philosophical Society, 60 (1): 1–5, Bibcode:1964PCPS...60....1B, doi:10.1017/s0305004100037385, MR 0158388, S2CID 122829092. <a href="/wiki/L._W._Beineke" target="_blank">/wiki/L._W._Beineke</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">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 href="/wiki/Petra_Mutzel" target="_blank">/wiki/Petra_Mutzel</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">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. <a href="/wiki/Joan_Hutchinson" target="_blank">/wiki/Joan_Hutchinson</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">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, MR 1079441 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">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, MR 2076570 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">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, ISBN 978-3-319-97684-6, MR 3930641 <a href="978-3-319-97684-6" target="_blank">978-3-319-97684-6</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Brass, Peter; Cenek, Eowyn; Duncan, Christian 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. <a href="/wiki/Anna_Lubiw" target="_blank">/wiki/Anna_Lubiw</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">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, ISBN 978-0-8218-3484-8, MR 2065254. <a href="978-0-8218-3484-8" target="_blank">978-0-8218-3484-8</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">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. <a href="/wiki/Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society" target="_blank">/wiki/Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
</ol>

Thickness (graph theory) open-in-new

Thickness (graph theory)