A matematika, azon belül a gráfelmélet területén egy gráf vastagsága (thickness) a síkbarajzolható gráfok minimális száma, amibe élei particionálhatók. Tehát, ha létezik ugyanazon a csúcshalmazon síkbarajzolható gráf, melyek uniója , akkor vastagsága legfeljebb ... Tehát a gráf vastagsága a síkbarajzolható részgráfok minimális száma, melyek uniója kiadja -t.Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009 Egy síkgráf vastagsága tehát 1. A 2 vastagságú gráfokat biplanáris gráfoknak (biplanar graphs) is nevezik. A vastagság fogalmát Frank Harary egy 1962-es sejtésében vezette be: eszerint bármely 9 csúcsú gráfra igaz, hogy vagy ő, vagy komplementere nem síkba rajzolható. A probléma ekvivalens azzal a felvetéssel, hogy a teljes gráf biplanáris-e (nem az, és a sejtés igaz). A gráfvastagság terén az 1998-as állapotokat részletesen szemléző cikket Petra Mutzel, Thomas Odenthal és Mark Scharbrodt szerezték.Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey
Specifikus gráfok A teljes gráf vastagsága
kivéve az esetet, akkor három., Theorem 3.2..
Néhány kivétellel a teljes páros gráf vastagsága: , Theorem 3.4..
A hiperkockagráf vastagsága:
Kapcsolódó problémák Minden erdő síkgráf, és minden síkgráf legfeljebb három erdőre particionálható. Így tehát bármely gráf vastagsága legfeljebb ugyanazon gráf arboricitásával (az erdők számával, melybe particionálható), legalább az arboricitás harmadával egyenlő.. vastagsága konstans faktorra van egy másik gyakran használt gráfinvariánssal, a degeneráltsággal is, ami összes részgráfjában a fokszám minimális értékeinek a maximuma. Ha egy csúcsú gráf vastagsága t, akkor legfeljebb éle lehet, tehát degeneráltsága is legfeljebb . A másik irányban, ha egy gráf degeneráltsága , akkor arboricitása és vastagsága is legfeljebb .
A vastagság közeli kapcsolatban van a szimultán beágyazás problémájával.. Ha két vagy több síkbarajzolható gráf csúcshalmazai megegyeznek, akkor lehetséges ezen gráfok egyidejű síkbaágyazása oly módon, hogy az élek görbe vonalúak (a csúcsok pedig megegyeznek). Ez nem feltétlenül lehetséges az élek egyenes szakaszokkal történő lerajzolásakor.
Egy másik gráfinvariáns, a gráf egyenes vonalú vastagsága, rektilineáris vastagsága vagy mértani vastagsága (rectilinear thickness, geometric thickness) meghatározza a síkbarajzolható gráfok legkisebb számát, melyekbe oly módon felosztható, hogy a gráfok szimultán módon, egyenes vonalakkal lerajzolhatók legyenek. A könyvvastagság további megszorítással él, miszerint az összes csúcsnak konvex helyzetben kell lennie, körkörös elrendezést alkotva. Az arboricitástól és a degeneráltságtól eltérően ezek az invariánsok egyike sincsen konstans faktorra a másiktól..
Számítási bonyolultság Adott gráf vastagságának meghatározása NP-nehéz, annak meghatározása, hogy a vastagság legfeljebb kettő, NP-teljes.. Az arboricitással való kapcsolat miatt azonban a gráf vastagsága 3 közelítési aránnyal polinom időben meghatározható.
Fordítás
Kapcsolódó szócikkek 1-síkbarajzolható gráf
Jegyzetek
Kategória:Gráfinvariánsok Kategória:Síkgráfok