Faszélesség forrásának megtekintése

A [[matematika]], azon belül a [[gráfelmélet]] területén egy [[irányítatlan gráf]] '''faszélessége''' vagy '''favastagsága''' ''(treewidth)'' egy a gráf szerkezetétől függő, a gráfhoz rendelt szám, azaz [[gráftulajdonság]]. A faszélesség több, egymással egyenértékű módon definiálható: a gráf [[fafelbontás]]a legnagyobb csúcshalmazával, a gráf [[merev körű kiegészítés]]ében található legnagyobb [[klikk (gráfelmélet)|klikkel]], a gráfon játszott [[üldözős-menekülős játék]] elkerülési stratégiáját leíró [[menedék (gráfelmélet)|menedékkel]] vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz [[bramble]]-ök maximális rendjével.

A faszélesség gyakran előkerül gráfalgoritmusok [[parametrikus bonyolultság]]ának vizsgálatakor. A legfeljebb ''k'' faszélességű gráfokat [[részleges k-fa|részleges ''k''-fáknak]] is nevezik; számos, részletekbe menően tanulmányozott gráfcsalád rendelkezik korlátozott faszélességgel.

A faszélesség koncepciója először {{harvs|last1 = Bertelé|first1=Umberto|last2=Brioschi|first2=Francesco|year = 1972|txt}}-nél jelent meg „dimenzió” név alatt. Később {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}} fedezte fel újra, a [[Hadwiger-szám]]mal közös tulajdonságai alapján. Majd {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (matematikus)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} ismét felfedezték, és azóta számos más szerző is tanulmányozta.<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>

==Definíció==
[[Image:Tree decomposition.svg|thumb|240px|Nyolc csúcsú gráf (fent), fafelbontása hat csomópontú fába (lent). A gráf minden éle olyan két csúcsot köt össze, melyek valamely fa-csomóponton együtt szerepelnek, továbbá minden egyes csúcs olyan fa-csomópontokon szerepel, melyek a fa folytonos részfáját alkotják. Minden fa-csomóponton legalább három csúcs szerepel, ezért ennek a felbontásnak a szélessége kettő.]]
Egy ''G'' = (''V'', ''E'') gráf [[fafelbontás]]a alatt olyan ''T'' fát értünk, az ''X''<sub>1</sub>, ..., ''X''<sub>''n''</sub> csomópontokkal, ahol mindegyik ''X''<sub>''i''</sub> a ''V'' részhalmaza, mely a következő tulajdonságoknak megfelel<ref>{{harvtxt|Diestel|2005}} section 12.3</ref> (a ''csomópont'' alatt ''T'' egy-egy csúcsát értjük, hogy elkerüljük a ''G'' csúcsaival való összekeverésüket):
# Az ''X''<sub>''i''</sub> halmazok uniója megegyezik ''V''-vel. Tehát a gráf minden csúcsát tartalmazza legalább egy facsomópont.
# Ha ''X''<sub>''i''</sub> és ''X''<sub>''j''</sub> is tartalmaz egy ''v'' csúcsot, akkor az ''X''<sub>''i''</sub> és ''X''<sub>''j''</sub> közötti (egyedi) úton lévő minden ''T''-beli ''X''<sub>''k''</sub> csomópontnak is tartalmaznia kell ''v''-t. Ezzel ekvivalens megfogalmazás szerint, a ''v''-t tartalmazó facsomópontok a ''T'' összefüggő részfáját alkotják.
# A gráf minden (''v'', ''w'') éléhez tartozik egy ''X''<sub>''i''</sub> részhalmaz, ami ''v''-t és ''w''-t is tartalmazza. Tehát a gráf csúcsai akkor lehetnek szomszédosak, ha a nekik megfelelő részfáknak van egy közös csomópontja.
A fafelbontás ''szélessége'' a legnagyobb ''X''<sub>''i''</sub> halmaz mérete mínusz egy. A ''G'' gráf tw(''G'') '''faszélessége''' a ''G'' összes lehetséges fafelbontásai közül a minimális szélesség. Ebben a definícióban azért csökkentjük eggyel a legnagyobb halmaz méretét, hogy egy fa szélessége éppen eggyel legyen egyenlő.

Ezzel ekvivalens definíció szerint a ''G'' faszélessége eggyel kisebb, mint a legkisebb [[maximális elemszámú klikk|klikkszámú]], ''G''-t tartalmazó [[merev körű gráf]] legnagyobb [[klikk (gráfelmélet)|klikkje]]. Ilyen klikkméretű merev körű gráfot elő lehet állítani úgy, hogy ''G''-nek minden olyan két csúcsa közé behúzunk egy élt, melyek közül mindkettő legalább egy halmazba beletartozik az ''X<sub>i</sub>''-t közül.

A faszélesség jellemezhető az [[üldözős-menekülős játék]] elkerülési stratégiáját leíró [[menedék (gráfelmélet)|menedékek]] segítségével is. Egy ''G'' gráf faszélessége pontosan akkor ''k'', ha létezik benne {{nowrap|''k'' + 1}} rendű menedék, de magasabb rendű már nem. Egy {{nowrap|''k'' + 1}} rendű menedék olyan ''β'' függvény, ami ''G'' minden, legfeljebb ''k'' csúcsot tartalmazó ''X'' csúcshalmazához hozzárendeli {{nowrap|''G'' \ ''X''}} valamely összefüggő komponensét, és amire igaz az a monotonitási feltétel, miszerint ha {{nowrap|''X'' ⊆ ''Y''}}, akkor {{nowrap|''&beta;''(''Y'') ⊆ ''&beta;''(''X'')}}.

[[File:3x3 grid graph haven.svg|thumb|A 3×3-as rácsgráfhoz tartozó 4 rendű [[bramble]], melynek létezése igazolja, hogy a gráf faszélessége legalább&nbsp;3]]
Hasonló jellemzés adható az egymást kölcsönösen érintő (vagy közös csúccsal rendelkező, vagy éllel összekötött) összefüggő részgráfok, a [[bramble]]-ök segítségével.<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref> A bramble rendje a részgráfok családjának legkisebb „hitting set”-je (olyan halmaz, ami minden halmaz elemei közül legalább egyet tartalmaz), a gráf faszélessége pedig eggyel kisebb a bramble maximális rendjénél.

==Példák==
Minden ''K<sub>n</sub>'' [[teljes gráf]] faszélessége ''n''&nbsp;&minus;&nbsp;1. Ez a legkönnyebben a merev körű gráfos definícióból látható be: a teljes gráf eleve merev körű, és újabb él hozzáadásával nem lehet csökkenteni a legnagyobb klikkjének a méretét.

Egy összefüggő, legalább két csúcsból álló gráf faszélessége pontosan akkor 1, ha a gráf fa. A fa szélessége a teljes gráfokhoz hasonlóan látható be (merev körű, és maximális elemszámú klikkje 2). Megfordítva, ha egy gráfnak van köre, akkor a gráf minden [[merev körű kiegészítés]]ében legalább egy háromszög egymást követő csúcsa szerepel, amiből következik, hogy a faszélesség legalább kettő.

==Korlátos faszélesség==

===Korlátos faszélességű gráfcsaládok===
Rögzített ''k'' értékekre, a legfeljebb ''k'' faszélességű gráfokat [[részleges k-fa|részleges ''k''-fáknak]] nevezik. A korlátos faszélességű gráfcsaládok közé tartoznak a [[kaktuszgráf]]ok, [[pszeudoerdő]]k, [[soros-párhuzamos gráf]]ok, [[külsíkgráf]]ok, [[Halin-gráf]]ok és [[Apollóniusz-hálózat]]ok.<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> A [[strukturált programozás|strukturált programok]] [[Fordítóprogram|lefordításakor]] létrejövő [[vezérlésfolyam-gráf]] faszélessége szintén korlátos, ami lehetővé teszi bizonyos feladatok, például a [[regiszterallokáció]] hatékony végrehajtását.<ref>{{harvtxt|Thorup|1998}}.</ref>

A [[síkbarajzolható gráf]]ok faszélessége nem korlátos, hiszen az ''n'' &times; ''n''-es [[rácsgráf]] olyan síkbarajzolható gráf, melynek faszélessége pontosan ''n''. Ezért ha ''F'' egy korlátos faszélességű, minorzárt gráfcsalád, akkor nem tartalmazhatja az összes síkbarajzolható gráfot. Megfordítva, ha valamely síkbarajzolható gráf nem jelenik meg egy ''F'' gráfcsalád minoraként, akkor létezik olyan ''k'' konstans, melyre az összes ''F''-beli gráf faszélessége legfeljebb ''k''. Más szavakkal, a következő három feltétel egymással egyenértékű:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
#''F'' korlátozott faszélességű gráfok minorzárt családja;
#Az ''F''-et jellemző véges sor tiltott minor közül valamelyik síkba rajzolható;
#''F'' minorzárt gráfcsalád, ami nem tartalmazza az összes síkbarajzolható gráfot.

===Tiltott minorok===
[[File:Partial 3-tree forbidden minors.svg|thumb|300px|A 3 faszélesség négy tiltott minora: ''K''<sub>5</sub> (fent balra), az oktaédergráf (lent balra), a Wagner-gráf (fent jobbra) és az ötszögű hasábgráf (lent jobbra)]]
Minden véges ''k'' értékre a legfeljebb ''k'' faszélességű gráfok jellemezhetők [[Tiltott gráfok szerinti osztályozás|tiltott minorok]] egy véges halmazával. (Tehát bármely ''k''-nál nagyobb faszélességű gráf tartalmazza ezen obstrukciós halmaz tiltott gráfjainak valamelyikét minorként.) Minden ilyen véges obstrukciós halmaz tartalmaz legalább egy síkbarajzolható gráfot.
*A ''k'' = 1 esetben az egyedüli tiltott minor a 3 csúcsú [[körgráf]], ''K''<sub>3</sub>.<ref name="b88">{{harvtxt|Bodlaender|1988}}.</ref>
*A ''k'' = 2 esetben az egyedüli tiltott minor a 4 csúcsú teljes gráf, ''K''<sub>4</sub>.<ref name="b88"/>
*A ''k'' = 3 esetben már négy tiltott minor van: a ''K''<sub>5</sub> teljes gráf, az [[oktaéder]] gráfja, a ''GP''(5,1)  [[ötszög alapú hasáb|ötszög alapú]] [[hasábgráf]] és a [[Wagner-gráf]]. Ezek  közül a két [[poliédergráf]] síkba rajzolható.<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
A ''k'' = 4 esetben már legalább 75 tiltott minort találtak, és a ''k'' növekedésével a tiltott minorok száma legalább a ''k'' négyzetgyöke szerint exponenciálisan nő.{{sfnp|Ramachandramurthi|1997}} Az ismert felső korlátok a tiltott minorok méretére és számára azonban sokkal nagyobbak ennél az alsó korlátnál.{{sfnp|Lagergren|1993}}

==Algoritmusok==

===A faszélesség meghatározása===
Annak meghatározása, hogy adott ''G'' gráf faszélessége adott ''k'' értékét meghaladja-e, NP-teljes probléma.{{sfnp|Arnborg|Corneil|Proskurowski|1987}}
Ennek ellenére ''k'' rögzített értékére a pontosan ''k'' faszélességű gráfok felismerhetők, és ''k'' szélességű fafelbontásuk is előállítható lineáris időben.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> Ezen algoritmus időfüggése ''k'' szerint exponenciális.

{{megoldatlan|A|matematika|Meghatározható-e a [[síkbarajzolható gráf]]ok faszélessége polinom időben?}}
Nem ismert, hogy a [[síkbarajzolható gráf]]ok faszélességének meghatározása NP-teljes, vagy polinom időben meghatározható-e.{{sfnp|Kao|2008}}

A gyakorlatban {{harvtxt|Shoikhet|Geiger|1997}} algoritmusa képes a legfeljebb 100 csúcsból álló gráfok faszélességének meghatározására legfeljebb 11 értékig, optimális faszélességű merev körű kiegészítés keresésével.

===Egyéb problémák megoldása alacsony faszélességű gráfokon===
Az 1970-es évek elején megfigyelték, hogy a gráfokon definiált kombinatorikai optimalizációs problémák nagy osztálya hatékonyan megoldható nem soros, [[dinamikus programozás]]i módszerekkel, amennyiben a gráf korlátos „dimenzióval” rendelkezik,{{sfnp|Bertelé|Brioschi|1972}} mely paraméterről {{harvtxt|Bodlaender|1998}} megmutatta, hogy a faszélességgel ekvivalens. Később egymástól függetlenül több szerző is megfigyelte az 1980-as évek végén,<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> hogy számos, tetszőleges gráfokon [[NP-teljes]] probléma a korlátos faszélességű gráfokon [[dinamikus programozás]]sal hatékonyan megoldható, a gráfok fafelbontásának felhasználásával.

Példa erre a ''k'' faszélességű gráf [[gráfok színezése|színezése]]. A fafelbontás minden ''X<sub>i</sub>'' halmazára, és az ''X<sub>i</sub>'' csúcsainak minden színosztályba sorolására az algoritmus meghatározza, hogy a színezés érvényes-e, illetve kiterjeszthető-e a a felbontás leszármazó csomópontjaira, a csomópontokon tárolt hasonló információk felhasználásával. A végső algoritmus egy ''n'' csúcsú gráf optimális színezését O(''k''<sup>''k''&nbsp;+&nbsp;O(1)</sup>''n'') időben oldja meg, ami ezt a problémát [[parametrikus bonyolultság|rögzített paraméter mellett kezelhetővé]] teszi.

===Courcelle-tétel===
{{fő|Courcelle-tétel}}
Egy nagy problémaosztályra létezik lineáris idejű megoldó algoritmus, ha bemenetként egy konstans, korlátos faszélességű [[fafelbontás]]t adunk meg. A [[Courcelle-tétel]]<ref>{{Cite journal|url = |title = The monadic second-order logic of graphs I: Recognizable sets of finite graphs|last = Courcelle|first = B.|date = 1990|journal = Information and Computation|doi = 10.1016/0890-5401(90)90043-h|pmid = |access-date = |volume = 85|pages = 12–75|issue = |citeseerx = 10.1.1.158.5595}}</ref><ref>{{Cite journal|url = |title = The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.|last = Courcelle|first = B.|date = 1992|journal = Informatique Théorique|doi = |pmid = |access-date = |edition = |pages = 257–286|issue = 26}}</ref> állítása szerint ha egy gráfprobléma kifejezhető [[monadikus másodrendű logika]] szerinti [[gráflogika]] segítségével, akkor korlátos faszélességű gráfokon lineáris időben megoldható. A monadikus másodrendű logika a gráftulajdonságokat a következő konstrukciók segítségével írja le: logikai műveletek (<math> \wedge ,\vee ,\neg ,\Rightarrow </math>), tartalmazás ellenőrzése (pl. <math> e \in E, v \in V </math>), kvantorok csúcsokra és élekre, illetve csúcsok és élek halmazára (pl. <math>\forall</math>  <math>v \in V</math>, <math>\exists</math> <math>e \in E</math>, <math>\exists</math>  <math>I \subseteq V</math>,  <math>\forall</math>  <math>F \subseteq E </math>), illeszkedés ellenőrzése (''u'' az ''e'' végpontja), valamint egy optimalizáló kiterjesztés.

Tekintsük például a gráfok [[gráfok színezése|3-színezési problémáját]]. Egy <math>G=(V,E)</math> gráf esetén azt kérdezzük, lehetséges-e minden <math>v \in V</math> csúcshoz a 3 szín egyikét hozzárendelni úgy, hogy semelyik két szomszédos csúcs ne legyen egymással megegyező színű.
A probléma így fejezhető ki monadikus másodrendű logikával:
:<math> \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge </math>
:<math> \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3))</math>, 
ahol <math>W_1, W_2, W_3</math> az egyes színosztályba tartozó csúcs-részhalmazoknak felelnek meg.
Tehát Courcelle tétele szerint a 3-színezési probléma lineáris időben megoldható egy konstans faszélességű gráfon, ha annak fafelbontása adott.

==Kapcsolódó paraméterek==

===Útszélesség===
Egy gráf [[útszélesség]]e a faszélességhez nagyon hasonlóan definiálható, de olyan fafelbontásokra korlátozódik, melyben kizárólag [[útgráf]]ok szerepelnek. Alternatív megoldásként az útszélesség definiálható [[intervallumgráf]]ok segítségével, hasonlóan a faszélesség merev körű gráfokkal való definiálásához. A gráfok útszélessége az eddigiekből következően legalább akkora, mint a faszélességük, de legfeljebb logaritmikus faktorral lehet nagyobb.<ref name="b98"/> Egy másik paramétert, a [[gráf sávszélessége|sávszélességet]]  [[egység-intervallumgráf]]fal definiálják, és legalább akkora, mint az útszélesség. További kapcsolódó paraméter a [[fa mélysége|famélység]], ami egy minorzárt gráfcsaládnál akkor korlátos, ha a család  tiltott gráfja egy út, valamint a [[degeneráltság (gráfelmélet)|degeneráltság]], a gráfok ritkaságának egy mértéke, ami legfeljebb a faszélességgel egyezik meg.

===Rácsminor-méret===
Mivel egy ''n''&nbsp;&times;&nbsp;''n'' méretű négyzetes [[rácsgráf]] faszélessége ''n'', egy ''G'' gráf faszélessége mindig nagyobb vagy egyenlő, mint ''G'' legnagyobb rácsgráf-minorának mérete. Megfordítva, a [[Neil Robertson (matematikus)|Robertson]] és [[Paul Seymour (mathematician)|Seymour]] által kimondott rácsminor-tétel ''(grid minor theorem)'' szerint létezik olyan ''f'' függvény, melyre a faszélesség legfeljebb ''f''(''r''), ahol ''r'' a legnagyobb négyzetrács-minor mérete.<ref>Robertson, Seymour. ''Graph minors. V. Excluding a planar graph''. [http://www.sciencedirect.com/science/article/pii/0095895686900304] {{Open access}}</ref> Az ''f''-re vonatkozó legjobb korlátok szerint ''f'' legalább Ω(''r''<sup>''d''</sup>) valamely rögzített ''d''>0 konstansra, de legfeljebb O({{sqrt|''r''/log ''r''}}).<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}. Az alsó korlátban látható &Omega; jelöléshez lásd [[O jelölés]].</ref> Egyes korlátozott gráfcsaládokra szorosabb korlátok ismertek, melyekre vonatkozó gráfoptimalizálási problémákra hatékony algoritmusokat ad a [[bidimenzionalitás]]-elmélet.{{sfnp|Demaine|Hajiaghayi|2008}}
A [[Halin-rácstétel]] a faszélesség és rácsminor-méret között állít fel összefüggést végtelen gráfokra.{{sfnp|Diestel|2004}}

===Átmérő és lokális faszélesség===
Egy ''F'' gráfcsaládnak akkor van '''korlátos helyi faszélessége''' ''(bounded local treewidth)'', illetve rendelkezik az '''átmérő-faszélesség tulajdonsággal''' ''(diameter-treewidth property)'', ha a család gráfjainak faszélességét felülről korlátozza [[átmérő (gráfelmélet)|átmérőjük]] egy függvénye. Ha ''F'' minden minora szintén ''F''-ben található, akkor ''F'' pontosan akkor rendelkezik korlátos helyi faszélességgel, ha ''F'' valamelyik [[tiltott minor]]a egy [[csúcsgráf]].{{sfnp|Eppstein|2000}} Ennek az eredménynek az eredeti bizonyításában szerepelt annak bizonyítása is, hogy egy csúcsminor-mentes gráfcsalád faszélessége legfeljebb az átmérő dupla-exponenciális függvényében nő;<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref> ezt később sikerült sima exponenciálisra{{sfnp|Demaine|Hajiaghayi|2008}}, majd lineáris korlátra javítani.{{sfnp|Demaine|Hajiaghayi|2004b}}
Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a [[bidimenzionalitás]] algoritmikus elméletével,<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref> és minden elsőrendű logikával definiálható gráftulajdonság létezése egy csúcsminor-mentes gráfcsalád esetében eldönthető a lineárisnál csak kissé rosszabb – O(''n''<sup>''1+(1/k)''</sup> – időben.{{sfnp|Frick|Grohe|2001}}

Lehet korlátos helyi faszélessége nem minorzárt gráfosztálynak is. Ilyenek például az élenként legfeljebb egy metszéssel síkba rajzolható ún. [[1-síkbarajzolható gráf]]ok, vagy általánosabban azok a gráfok, melyek egy korlátos génuszú felületre élenként korlátozott számú metszéssel lerajzolhatók. Ahogy a minorzárt gráfcsaládoknál, a korlátos helyi faszélesség itt is hatékony approximációs algoritmusoknak enged utat.{{sfnp|Grigoriev|Bodlaender|2007}}

===Hadwiger-szám és ''S''-függvények===
{{harvtxt|Halin|1976}} egy általa ''S''-függvényeknek (''S''-functions) nevezett gráfparaméter-osztályt definiál, melybe a faszélesség is beletartozik. Ezeknek a gráfokhoz egész számokat rendelő függvényeknek a következő tulajdonságokkal kell rendelkezniük: az [[üres gráf]]on legyen nulla az értékük, legyenek [[gráfminor|minor-monotonok]],<ref>Az ''f'' függvény akkor minor-monoton, ha fennáll, hogy ha ''H'' a ''G'' minora,  akkor ''f(H) ≤ f(G)''.</ref> értékük eggyel nőjön, ha az összes korábbi csúccsal szomszédos új csúcs kerül a gráfba, végül hogy egy klikk-[[Elvágó csúcshalmaz|szeparátor]] két oldalán lévő részgráfok értékei közül a nagyobbikat vegye fel. Az összes ilyen függvény halmaza az elemenkénti minimalizáció és maximalizáció műveleteire nézve [[teljes háló]]t alkot. A háló legkisebb eleme a [[Hadwiger-szám]], azaz a legnagyobb teljesgráf-minor mérete, a legnagyobb pedig a faszélesség.

==Fordítás==
* {{fordítás|en|Treewidth|oldid=872112688|n=a|4=angol}}

==Jegyzetek==
{{jegyzetek}}
==Források==
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Corneil | first2 = D. | author2-link = Derek Corneil
 | last3 = Proskurowski | first3 = A.
 | title = Complexity of finding embeddings in a ''k''-tree
 | journal = SIAM Journal on Matrix Analysis and Applications
 | volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}
*{{citation
 | last1 = Arnborg | first1 = Stefan
 | last2 = Proskurowski | first2 = Andrzej
 | last3 = Corneil | first3 = Derek G. | author3-link = Derek Corneil
 | doi = 10.1016/0012-365X(90)90292-P
 | issue = 1
 | journal = Discrete Mathematics
 | mr = 1045920
 | pages = 1–19
 | title = Forbidden minors characterization of partial 3-trees
 | volume = 80
 | year = 1990}}
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial ''k''-trees
 | journal = Discrete Applied Mathematics
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0}}
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}
*{{citation
 | last1 = Bertelé | first1 = Umberto
 | last2 = Brioschi | first2 = Francesco
 | title = Nonserial Dynamic Programming
 | year = 1972
 | publisher = Academic Press
 | isbn = 0-12-093450-7
 | pages = 37–38
 | url = https://books.google.ca/books?id=baw3LMwm-y8C&pg=PA37}}
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110| citeseerx = 10.1.1.18.8503}}
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | title = A linear time algorithm for finding tree-decompositions of small treewidth
 | journal = SIAM Journal on Computing
 | volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219| citeseerx = 10.1.1.19.7484}}
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | title = A partial ''k''-arboretum of graphs with bounded treewidth
 | journal = Theoretical Computer Science
 | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4 | doi-access=free}}
*{{citation
 | last1 = Chekuri | first1 = Chandra
 | last2 = Chuzhoy | first2 = Julia | author2-link = Julia Chuzhoy
 | arxiv=1305.6577
 | doi = 10.1145/2820609
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 3593966
 | pages = A40:1–65
 | title = Polynomial bounds for the grid-minor theorem
 | volume = 63
 | year = 2016}}
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Hajiaghayi | first3 = MohammadTaghi
 | last4 = Thilikos | first4 = Dimitrios M.
 | year = 2004
 | doi = 10.1137/S0895480103433410
 | issue = 3
 | journal = SIAM Journal on Discrete Mathematics
 | mr = 2134412
 | pages = 501–511
 | title = Bidimensional parameters and local treewidth
 | volume = 18| citeseerx = 10.1.1.107.6195}}
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = Algorithmica
 | mr = 2080518
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | volume = 40
 | year = 2004a}}
*{{citation
 | last1 = Demaine | first1 = Erik D.
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | contribution = Equivalence of local treewidth and linear local treewidth and its algorithmic applications
 | location = New York
 | mr = 2290974
 | pages = 840–849
 | publisher = ACM
 | title = Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | year = 2004b}}
*{{citation
 | last1 = Demaine| first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi| first2 = MohammadTaghi 
 | doi = 10.1007/s00493-008-2140-4
 | issue = 1
 | journal = [[Combinatorica]]
 | pages = 19–36
 | title = Linearity of grid minors in treewidth with applications through bidimensionality
 | url = http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf
 | volume = 28
 | year = 2008}}
*{{citation
 | last = Diestel | first = Reinhard
 | doi = 10.1007/BF02941538
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | mr = 2112834
 | pages = 237–242
 | title = A short proof of Halin's grid theorem
 | volume = 74
 | year = 2004}}
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}}
*{{citation
 | last = Eppstein | first = D. | authorlink = David Eppstein
 | doi = 10.1007/s004530010020
 | issue = 3-4
 | journal = Algorithmica
 | mr = 1759751
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000| arxiv = math/9907126}}
*{{citation
 | last1 = Frick | first1 = Markus
 | last2 = Grohe | first2 = Martin
 | doi = 10.1145/504794.504798
 | issue = 6
 | journal = Journal of the ACM
 | mr = 2143836
 | pages = 1184–1206
 | title = Deciding first-order properties of locally tree-decomposable structures
 | volume = 48
 | year = 2001| arxiv = cs/0004007
 }}
*{{citation
 | last1 = Grigoriev | first1 = Alexander
 | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender
 | doi = 10.1007/s00453-007-0010-x
 | issue = 1
 | journal = Algorithmica
 | mr = 2344391
 | pages = 1–11
 | title = Algorithms for graphs embeddable with few crossings per edge
 | volume = 49
 | year = 2007| citeseerx = 10.1.1.65.5071}}
*{{Citation
 | title = ''S''-functions for graphs
 | year = 1976
 | last = Halin | first = Rudolf | authorlink = Rudolf Halin
 | journal = Journal of Geometry
 | pages = 171–186
 | volume = 8
 | doi=10.1007/BF01917434
}}
*{{citation|title=	Encyclopedia of Algorithms|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer|year=2008|isbn=9780387307701|contribution=Treewidth of graphs|page=969|url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969|quote=Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.}}
*{{citation
 | last = Lagergren | first = Jens
 | contribution = An upper bound on the size of an obstruction
 | doi = 10.1090/conm/147/01202
 | location = Providence, RI
 | mr = 1224734
 | pages = 601–621
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph structure theory (Seattle, WA, 1991)
 | volume = 147
 | year = 1993}}
*{{citation
 | last = Ramachandramurthi | first = Siddharthan
 | doi = 10.1137/S0895480195280010
 | issue = 1
 | journal = SIAM Journal on Discrete Mathematics
 | mr = 1430552
 | pages = 146–157
 | title = The structure and number of obstructions to treewidth
 | volume = 10
 | year = 1997}}
*{{citation
 | last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (matematikus)
 | title = Graph minors III: Planar tree-width
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 36
 | issue = 1 | year = 1984 | pages = 49–64
 | doi = 10.1016/0095-8956(84)90013-3}}
*{{citation
 | last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (matematikus)
 | title = Graph minors V: Excluding a planar graph
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 41 | issue = 1 | year = 1986 | pages = 92–114 | doi = 10.1016/0095-8956(86)90030-4}}
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (matematikus)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (matematikus)
 | doi = 10.1006/jctb.1994.1073
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1305057
 | pages = 323–348
 | title = Quickly excluding a planar graph
 | volume = 62
 | year = 1994}}
*{{citation
 | last1 = Satyanarayana | first1 = A.
 | last2 = Tung | first2 = L.
 | doi = 10.1002/net.3230200304
 | issue = 3
 | journal = Networks
 | mr = 1050503
 | pages = 299–322
 | title = A characterization of partial 3-trees
 | volume = 20
 | year = 1990}}
*{{citation
 | last1 = Seymour | first1 = Paul D. | authorlink1 = Paul Seymour (matematikus)
 | last2 = Thomas | first2 = Robin | author2-link=Robin Thomas (matematikus)
 | title = Graph Searching and a Min-Max Theorem for Tree-Width. 
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 58 | issue = 1 | pages = 22–33 | doi = 10.1006/jctb.1993.1027
 | year = 1993}}
*{{citation
 | last1 = Shoikhet | first1 = Kirill
 | last2 = Geiger | first2 = Dan
 | contribution = A practical algorithm for finding optimal triangulations
 | pages = 185–190
 | title = Proc. AAAI '97
 | url = http://www.aaai.org/Papers/AAAI/1997/AAAI97-029.pdf
 | year = 1997}}
*{{citation
 | last = Thorup | first = Mikkel | authorlink = Mikkel Thorup
 | title = All structured programs have small tree width and good register allocation
 | journal = Information and Computation
 | volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697}}
[[Kategória:Gráfinvariánsok]]
[[Kategória:Gráfminorok]]