Ugrás a tartalomhoz

Könyvbe ágyazás

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
(Könyvvastagság szócikkből átirányítva)
A K5 teljes gráf háromlapos könyvbe ágyazása. Mivel nem síkbarajzolható gráf, így nem lehet metszések nélkül kevesebb lapba beágyazni, ezért könyvvastagsága három.

A matematika, azon belül a gráfelmélet területén egy gráf könyvbe ágyazása (book embedding) a gráfok síkba ágyazásának általánosítása ugyanazon egyenes által határolt félsíkok gyűjteményébe, vagyis „könyvbe” történő beágyazásra. Általában elvárt, hogy a gráf csúcsai ezen a határoló egyenesen (a könyv „gerincén”) feküdjenek, az élek pedig a saját félsíkjukon belül maradjanak. Egy gráf könyvvastagsága (book thickness) az a legkisebb félsík-szám, amivel a gráfnak még lehetséges könyvbe ágyazása. Nevezik a gráf „lapszámának” vagy „oldalszámának” (pagenumber), „halomszámának” (stacknumber) vagy „rögzített külvastagságának” (fixed outerthickness) is. A könyvbe ágyazás segítségével egyéb gráfinvariánsokat is definiáltak, köztük a lapszélességet vagy oldalszélességet (pagewidth) és a könyv-metszési számot (book crossing number).

Egy n csúcsú gráf könyvvastagsága legfeljebb , teljes gráfok esetén pedig pontosan ennyi. Az egy könyvvastagságú gráfok a külsíkgráfok. A legfeljebb kettő könyvvastagságú gráfok a szubhamiltoni gráfok; a síkbarajzolható gráfok könyvvastagsága legfeljebb négy. Minden minorzárt gráfcsaládnak, különösen a korlátos faszélességgel vagy génusszal rendelkezőknek korlátos a könyvvastagsága. Egy konkrét gráf könyvvastagságának eldöntése NP-nehéz, akár ismert a csúcsok sorrendje a könyv gerince mentén, akár nem.

A könyvbe ágyazások tanulmányozásának egyik motivációja a VLSI-tervezés, melyben a beágyazás csúcsai egy elektronikus áramkör komponenseit, az élek pedig az azokat összekötő huzalozást jelképezik. A könyvbe ágyazás a gráfok lerajzolásában is szerepet kap, ahol a gráfok standard lerajzolási módjai közül kettő, az ívdiagramok és a körkörös elrendezések is a könyvbe ágyazás segítségével szerkeszthetők meg.

A közlekedéstervezésben a gyalogos és járművel történő közlekedés kiinduló és célpontjai, melyek közlekedési lámpáknál találkoznak és lépnek interakcióba egymással matematikailag egy gráf csúcsaiként modellezhetők, ahol az élek különböző kiindulási és célpontokat kötnek össze. Egy ilyen gráf könyvbe ágyazása segíthet olyan időbeosztás tervezésében, ahol a forgalom a lehető legkevesebb lámpaváltással halad át a kereszteződésen. A bioinformatika területén az RNS feltekeredett szerkezetével kapcsolatos problémákban az egylapos könyvbe ágyazások a nukleinsav másodlagos szerkezetének klasszikus formáit, a kétlaposak pedig a pszeudocsomókat testesítik meg. A könyvbe ágyazás további felhasználási területei az absztrakt algebra és a csomóelmélet.

Több nyitott kérdés van a könyvvastagsággal kapcsolatban. Nem ismert, hogy tetszőleges gráf könyvvastagságát korlátozza-e felosztásainak könyvvastagsága. Nem ismert egy gráf háromlapos könyvbe ágyazása létezésének a számítási bonyolultsága: nem tudjuk róla, hogy polinom időben megoldható lenne, sem azt, hogy NP-nehéz-e. És bár a síkbarajzolható gráf egyikének a könyvvastagsága sem haladja meg a négyet, eddig nem sikerült találni olyan síkbarajzolható gráfot, aminek a könyvvastagsága elérné a négyes értéket.

Története

[szerkesztés]

A könyv, mint topologikus tér gondolata először az 1960-as években, C. A. Persinger és Gail Atneosen munkáiban jelent meg.[1][2] Atneosen ebben a munkájában már foglalkozott gráfok könyvbe ágyazásával. Az általa tanulmányozott beágyazásoknál a más topologikus terekbe való gráfbeágyazásnál megszokott definíciót használta: a csúcsoknak különböző pontok felelnek meg, az éleknek görbék, és két él görbéjének csak az élek közös végpontjában lehet közös pontja.

Az 1970-es évek elején Paul C. Kainen és L. Taylor Ollmann egy szigorúbb beágyazási fogalmat használtak, és végül ez terjedt el általánosan. Az ő megfogalmazásuk szerint a gráf csúcsainak a könyv gerince mentén kell elhelyezkedniük, és minden él csak egyetlen oldalon foglalhat helyet.[3][4] A terület fejlődésének további mérföldköve volt az 1980-as évek végén Mihalis Yannakakis bizonyítása, miszerint a síkbarajzolható gráfok könyvvastagsága legfeljebb négy,[5][6] valamint az 1990-es évek végén a bioinformatika és a könyvbe ágyazások közötti szoros kapcsolódások felfedezése.[7]

Definíciók

[szerkesztés]
A K3,3 három ház–három kút-gráfnak nincs kétlapos könyvbe ágyazása, de az ábrán látható módon lerajzolható egy kétlapos könyvbe egyetlen metszéssel. Ezért kétlapos könyvmetszési száma 1.
A gyémántgráf ezen 1 lapos könyvbe ágyazásának 3 a lapszélessége, mivel a sárga nyíl három élt keresztez.

Egy könyv egy speciális topologikus tér, amit neveznek félsíkok kévéjének vagy legyezőjének is (fan of half-planes).[1][8] Egyetlen ℓ egyenesből áll, amit a könyv gerincének vagy hátának (spine/back) neveznek, amihez egy vagy több félsík, a könyv lapjai vagy oldalai (pages), illetve levelei (leaves) csatlakoznak,[9] melyek mindegyikét a gerinc határolja. A véges számú lapból álló könyvek beágyazhatók a háromdimenziós térbe, akár úgy, hogy az ℓ-t a Descartes-féle koordináta-rendszer z-tengelyének választjuk, a lapokat pedig a k félsíknak, melyek az xz síkkal bezárt síkszögei 2π/k egész számú többszörösei.[10]

Egy véges G B könyvbe való könyvbe rajzolása (book drawing) a G olyan lerajzolása B-re, melyben G minden csúcsa B gerincének egy pontjának felel meg, G minden élének pedig egy-egy B egyetlen oldalán elhelyezkedő görbe. A G gráf k-oldalú könyv-metszési száma (book crossing number) a k-lapú könyvbe rajzolásai közül a minimális metszési szám.[11]

Egy véges G gráf B könyvbe történő könyvbe ágyazása (book embedding) olyan könyvbe rajzolás, ami a G-nek B-be történő beágyazását adja. Más szavakkal, G olyan, B-be történő könyvbe rajzolása, ami nem tartalmaz metsző éleket. Minden véges gráf könyvbe ágyazható, ha a könyvnek elegendően nagy számú lapja van. Ez könnyen belátható, figyelembe véve az esetet, hogy a gráf minden élét külön oldalra helyezzük el. A G gráf könyvvastagsága (book thickness), lapszáma vagy oldalszáma (pagenumber), illetve halomszáma (stack number) a G könyvbe ágyazásához szükséges lapok minimális száma. Az oldalszámon kívül egy másik, a könyvbe ágyazás minőségét mérő paraméter az oldalszélesség vagy lapszélesség (pagewidth). Ez a maximális számú él, amit egy oldalon a gerincre merőleges félegyenes elmetszhet. Ezzel ekvivalens megfogalmazás szerint (olyan könyvbe ágyazásoknál, ahol minden él monoton görbeként van lerajzolva), az egy oldalon található olyan élek halmazának maximális elemszáma, melyekre igaz, hogy az élek végpontpárjai által meghatározott intervallumok mind metszik egymást.[12][13][14]

A definíciók működésének alapja, hogy egyik élnek sem szabad a könyv egynél több lapján helyet foglalnia. Ahogy már Atneosen is megfigyelte, ha ehelyett az élek a könyv gerincén keresztül átmehetnek egyik lapról a másikra, bármely gráf beágyazható egy három lapból álló könyvbe.[2][15][16] Egy ilyen háromlapos topologikus könyvbe ágyazás (topological book embedding) esetén, ahol a gerinc metszése megengedett, bármely gráf beágyazható legfeljebb élenként logaritmikus számú gerincmetszéssel,[15] és egyes gráfoknál szükség is van ennyire.[17]

Specifikus gráfok

[szerkesztés]

Ahogy az első ábra mutatja, a K5 teljes gráf könyvvastagsága három: mivel nem síkbarajzolható gráf, a könyvvastagság a kettőt meghaladja, de létezik háromlapos beágyazás. Általánosabban, bármely n ≥ 4 csúcsú teljes gráf könyvvastagsága pontosan . Ez az eredmény egyben felső korlátot ad az n-csúcsú gráfok lehetséges könyvvastagságára.[10]

A Kn teljes gráf kétlapos könyvmetszési száma

ami passzol Anthony Hill bizonyítatlan sejtéséhez, ami ezen gráfok korlátozatlan metszési számára vonatkozik. Ha Hill sejtése igaz, akkor ennek a gráfnak a metszéseket minimalizáló lerajzolása kétlapos lerajzolásnál történne.[18]

A Ka,b teljes páros gráf könyvvastagsága legfeljebb min(a,b). Egy ilyen vastagságú lerajzolás megszerkesztéséhez a bipartíció kisebbik oldalán lévő csúcsok esetén a csúcsokból kiinduló éleket a saját lapjukra helyezzük el. Ez a korlát nem mindig éles, például a K4,4 könyvvastagsága három, nem négy. Ha a gráf két partíciója nagyon kiegyensúlyozatlan, ahol b > a(a − 1), akkor a Ka,b könyvvastagsága pontosan a.[10][19]

A T(kr,r) Turán-gráf (egy Kk,k,... teljes többrészes gráf, amit r független csúcshalmaz alkot halmazonként k csúccsal, élek pedig a különböző független halmazok csúcsai között húzódnak) t könyvvastagságára a következő egyenlőtlenség ismert:

és ha r páratlan, a felső korlát így javítható:

[10][20]

A bináris De Bruijn-gráfok, a keverés-csere gráfok (shuffle-exchange graph), és a gyűrűs kockák (amikor elég nagyok, hogy ne legyenek síkba rajzolhatók) könyvvastagsága pontosan három.[21]

Tulajdonságok

[szerkesztés]

Síkbarajzolhatóság és outerplanaritás

[szerkesztés]
Goldner–Harary-gráf, egy síkbarajzolható gráf hármas könyvvastagsággal

Adott G gráf könyvvastagsága pontosan akkor nem nagyobb egynél, ha G egy külsíkgráf. A külsíkgráfok ismérve, hogy van olyan síkba rajzolásuk, melynek az összes csúcsa a lerajzolás külső tartományához tartozik. Ilyen gráf esetén a külső tartományon való elhelyezkedés sorrendjében elhelyezve a csúcsokat a könyv gerincén meg is kapjuk a gráf egylapos könyvbe ágyazását. (A gráf egy artikulációs pontja többször is meg fog jelenni a csúcsok külső tartomány körüli ciklikus rendezésében, de a könyvbe ágyazásban csak egy kópiát kell elhelyezni.) Megfordítva, egy egylapos könyvbe ágyazás automatikusan külsík-beágyazás. Hiszen, ha egy gráf egyetlen lapon van beágyazva, és még egy félsíkot csatolunk a gerinchez, hogy a félsíkot teljes síkká egészítse ki, akkor a beágyazás külső tartománya magába foglalja a teljes hozzáadott félsíkot, és a csúcsok mind ezen a külső tartományon vannak.[10][12]

Bármely kétlapos könyvbe ágyazás tekinthető a síkba ágyazás speciális esetének, hiszen a könyv két lapjának az uniója a teljes síkkal ekvivalens topologikus teret ad ki. Ezért egy kettő könyvvastagságú gráf automatikusan síkbarajzolható gráf. Precízebben, a G gráf könyvvastagsága pontosan akkor nem haladja meg a kettőt, ha G részgráfja egy Hamilton-körrel rendelkező síkbarajzolható gráfnak, azaz szubhamiltoni.[10] Ha adott egy gráf kétlapos beágyazásával együtt, úgy egészíthető ki síkbarajzolható és Hamilton-körrel rendelkező gráffá, hogy bármelyik lapon extra éleket helyezünk el a gerincen egymás után következő, de még össze nem kötött csúcsok közé, valamint az első és utolsó csúcs közé. A Goldner–Harary-gráf példa olyan síkbarajzolható gráfra, aminek kettőnél nagyobb a könyvvastagsága: maximális síkbarajzolható, ezért nem adható hozzá él a síkba rajzolhatóság fenntartásával, és nincs Hamilton-köre.[10] Mivel a Hamilton-körök segítségével karakterizálhatók, a kétlapos beágyazással rendelkező gráfokat szubhamiltoni gráfoknak is nevezik.[12]

A matematika megoldatlan problémája:
Mekkora egy síkbarajzolható gráf maximális könyvvastagsága?
(A matematika további megoldatlan problémái)

A legfeljebb négy maximális fokszámú síkbarajzolható gráfok könyvvastagsága legfeljebb kettő.[22] Az Apollóniusz-hálózatok (síkbarajzolható 3-fák) könyvvastagsága legfeljebb három.[23] Általánosabban, a síkbarajzolható gráfok könyvvastagsága legfeljebb négy.[5][6] 1986-ban Mihalis Yannakakis azt a sejtést mondta ki,[6] miszerint léteznek olyan síkbarajzolható gráfok, melyek könyvvastagsága fel is veszi a négy értéket. Állításának beharangozott bizonyítása[5] azonban egészen 2020-ig nem látott napvilágot.[24] Ezért (Dujmović & Wood 2007) a síkbarajzolható gráfok maximális könyvvastagságának kérdését a megoldatlan problémák között sorolja fel.[25]

Viselkedés felosztás esetén

[szerkesztés]
A matematika megoldatlan problémája:
Korlátozhatja-e egy gráf könyvvastagságát felosztásai könyvvastagságának függvénye?
(A matematika további megoldatlan problémái)
A gyémántgráf könyvvastagsága éleinek felosztásával növekszik

Ha egy gráf minden élét egy-egy új csúcs beiktatásával két él hosszú utakra osztjuk fel, a gráf könyvvastagsága egyes esetekben megnövekszik. Például a gyémántgráf könyvvastagsága egy (mert külsíkgráf), felosztásának viszont kettő (síkbarajzolható, szubhamiltoni, de nem külsíkgráf). A felosztási folyamat azonban egyes esetekben jelentősen csökkentheti is a felosztott gráf könyvvastagságát. Például a Kn teljes gráf könyvvastagsága csúcsainak számával arányos, de az összes él felosztásával kapott gráf könyvvastagsága jóval kisebb, mindössze .[26] Az ilyen példák létezése ellenére, (Blankenship & Oporowski 1999) sejtése szerint a felosztás könyvvastagsága nem lehet sokkal kisebb az eredeti gráfénál. A sejtés szerint létezik olyan f függvény, hogy minden G gráfra és minden élének kettéosztásával kapott H gráfra igaz, hogy ha H könyvvastagsága t, akkor G könyvvastagsága legfeljebb f(t).[16] Ez a Blankenship–Oporowski-sejtés jelenleg (2018) bizonyítatlan.[27]

Más gráfinvariánsokkal való kapcsolata

[szerkesztés]

A könyvvastagság közeli rokona a vastagságnak, ami a síkbarajzolható gráfok minimális száma, amibe adott gráf élei particionálhatók. Egy G gráf vastagsága θ, ha lerajzolható a síkba, és élei kiszínezhetők θ színnel úgy, hogy azonos színű élek ne találkozzanak. Hasonlóan, a G gráf könyvvastagsága θ, ha lerajzolható egy félsíkba úgy, hogy csúcsai a félsík határán legyenek, élei pedig θ színnel legyenek színezve azonos színű élek találkozása nélkül. A könyvvastagság ezen megfogalmazásában az élek színei a könyvbe ágyazás lapjainak felelnek meg. A vastagság és a könyvvastagság értéke azonban nagyon különböző is lehet. Léteznek olyan teljes gráf-felosztások, melyek könyvvastagsága korlátlan,[15][16][26] bár vastagságuk mindössze kettő.[26]

A k faszélességű gráfok könyvvastagsága legfeljebb k + 1[25][28] és ez a korlát k > 2-re éles.[25] Az m éllel rendelkező gráfok könyvvastagsága ,[29] és a g génuszú gráfok könyvvastagsága .[30] Általánosabban, minden minorzárt gráfcsalád könyvvastagsága korlátos.[31][32] Másrészről, az 1-síkbarajzolható gráfok családja, bár nem minorzárt,[31] szintén korlátos könyvvastagságú,[33] bár egyes 1-síkbarajzolható gráfok, mint a K2,2,2,2 könyvvastagsága legalább négy.[34]

Egy korlátos könyvvastagságú gráf minden sekély minora ritka gráf, ahol az él/csúcs arányt korlátozó konstans kizárólag a minor mélységétől és a könyvvastagságtól függ. Tehát, (Nešetřil & Ossona de Mendez 2012) terminológiája szerint, a korlátos könyvvastagságú gráfok korlátos expanziójúak.[31] De még a korlátos fokszámú gráfoknak – ami a korlátos expanziónál sokkal szigorúbb követelmény – is lehet korlátlan könyvvastagsága.[35]

Mivel a kettő könyvvastagságú gráfok a síkbarajzolható gráfok, vonatkozik rájuk a síkgráf-elválasztási tétel: a csúcsaik közül választhatók olyan részhalmazok, a szeparátorok, melyek eltávolításával a gráf szétesik legfeljebb 2n/3 csúcsból álló részekre, ahol a szeparátorban legfeljebb csúcs található. Itt n a gráf csúcsainak számára utal. Léteznek azonban olyan, három könyvvastagságú gráfok, melyek nem rendelkeznek szublineáris méretű szeparátorral.[36]

A könyvbe ágyazás egy lapján található élek bizonyos szempontból úgy viselkednek, mint a verem adatszerkezet. Ez formálisan úgy fogalmazható meg, ha tekintjük egy verem push és pop műveleteinek tetszőleges sorozatát, majd vesszük a gráfot, melynek csúcsai a verem műveleteinek felelnek meg, a csúcsok a műveletek sorrendjében elhelyezve egy könyvbe ágyazás gerincén. Ekkor ha minden, a veremből kivételt végző pop művelettől húzunk egy élt az ugyanazt az objektumot a verembe elrakó push műveletig, az eredménygráfnak automatikusan létezni fog egylapos beágyazása. Ez az oka, hogy a gráf oldalszámát veremszámnak (stack number) is nevezik. Hasonlóan tekinthetjük egy sor (queue) sorba illesztési és sorból kivételi műveleteit, illetve az ebből képezett gráfot is; ebben a gráfban bármely két él vagy metszi egymást, vagy a gerincen diszjunkt intervallumokat fednek le. Az analógia alapján egy gráf sorba ágyazását (queue embedding) úgy definiálták, mint egy topologikus könyvbe való beágyazást, ahol minden csúcs a könyv gerincén van, minden él egyetlen lapon található és két azonos lapon lévő él vagy metszi egymást vagy a gerinc diszjunkt intervallumait fedik le. Egy gráf sorba ágyazásához szükséges lapok minimális száma a gráf sorba állítási száma (queue number).[31][37][38]

Számítási bonyolultság

[szerkesztés]
Egy húrmetszetgráf, a kör húrjainak metszetgráfja. Rögzített csúcssorrendű könyvbe ágyazásoknál a könyvvastagság kiszámítása ekvivalens a származtatott körmetszetgráf színezésével.

Egy gráf könyvvastagságának megkeresése NP-nehéz. Ez következik abból, hogy a maximális síkbarajzolható gráfok Hamilton-köreinek keresése NP-teljes. Egy maximális síkbarajzolható gráfban a könyvvastagság pontosan akkor kettő, ha a gráfnak van Hamilton-köre. Ezért adott maximális síkbarajzolható gráf könyvvastagságának tesztelése is NP-teljes.[39]

Ha egy gráf könyvbe ágyazása csúcsainak sorrendje rögzített, akkor egy kétlapos beágyazás (ha létezik) lineáris időben megtalálható, az adott gráf csúcsait a gerinc mentén történő rendezés sorrendjében összekötő körrel kiegészítve kapott gráf síkgráfságának tesztelésével.[7] (Unger 1992) állítása szerint a rögzített gerinc mentén történő rendezés háromlapos könyvbe ágyazása is polinom időben előállítható, bár írása számos részletet mellőz.[40] A négy vagy több lapot igénylő gráfoknál viszont a minimális lehetséges lapra történő beágyazás problémája NP-nehéz marad, a húrmetszetgráfok ekvivalens színezési problémájának NP-nehézsége miatt. Ha adott G gráf, csúcsainak a gerinc mentén történő rendezésével, ezeket a csúcsokat ugyanilyen sorrendben egy kör köré rajzolva, majd G éleit szakaszokként behúzva a G-t reprezentáló húrok jönnek létre. Ezekből húrmetszetgráf képezhető, aminek csúcsai az iménti ábra húrjai, élei pedig az egymást metsző húroknak feleltethetők meg. A húrmetszetgráf egy színezése G éleinek olyan részhalmazokba particionálása, melyek egy lapon metszés nélkül lerajzolhatók. Ezért az optimális színezés ekvivalens az optimális könyvbe ágyazással. Mivel a húrmetszetgráfok színezése négy vagy több szín esetén NP-nehéz, és mivel minden húrmetszetgráf megalkotható így valamely könyvbe ágyazási problémából kiindulva, ezért az optimális könyvbe ágyazás szintén NP-nehéz.[41][42][43] Kétlapos könyvbe ágyazás a gerincen rögzített csúcssorrendjét tekintve a metszések számának minimalizálása NP-nehéz még akkor is, ha ez a szám nem nulla.[42]

Ha a gerincen a csúcssorrend ismeretlen, de az élek két lapra történő elosztása adott, akkor lineáris időben megkereshető a két lapos beágyazás (ha létezik) SPQR-fák alapján.[44][45] Ha azonban sem a gerincen a csúcsok sorrendje, se az élek elosztása nem adott, akkor a két lapos beágyazás megtalálása NP-teljes. A könyv-metszési szám megkeresése szintén NP-teljes, mivel a speciális eset tesztelése, hogy a kétlapos metszési szám nulla-e, szintén NP-teljes.

A korlátos expanzió következményeként a részgráfizomorfizmus-probléma, annak tesztelése, hogy valamely korlátos méretű mintázat előfordul-e egy nagyobb gráfban, lineáris időben megoldható, ha a nagyobb gráfnak korlátos a könyvvastagsága. Ugyanez igaz akkor is, ha a nagyobb gráf feszített részgráfját vagy homeomorfizmusát keressük.[46][47] Ugyanezen okból, a korlátos könyvvastagságú gráfokon annak vizsgálata, hogy a gráfra igaz-e egy elsőrendű nyelven megfogalmazott formula, rögzített paraméter mellett kezelhető.[48]

(Bekos, Kaufmann & Zielke 2015) leírnak egy komplex rendszert az optimális könyvbe ágyazások megkeresésére, ami először a problémát átalakítja kielégíthetőségi problémává, amit egy SAT-megoldóval próbál megoldani. Állításuk szerint rendszerük képes volt 20 perc alatt megtalálni egy 400 csúcsú maximális síkbarajzolható gráf optimális beágyazását, valamint sikeresen alkalmazták egy 600 csúcsú gráfra, ami Yannanakis szerint négy lapot igényel a beágyazáshoz, de kiderült, hogy három is elegendő volt rá.[34]

Alkalmazások

[szerkesztés]

Hibatűrő többprocesszoros működés

[szerkesztés]

A könyvbe ágyazások tanulmányozásának (Chung, Leighton & Rosenberg 1987) által említett egyik fő motivációja a VLSI-tervezéssel kapcsolatos, a hibatűrő többprocesszoros rendszerek kialakításában. A szerzők által kifejlesztett DIOGENES rendszerben a többprocesszoros rendszer CPU-i a könyv gerincén található sorrend szerinti logikai sorrendbe rendeződnek (bár ez nem feltétlenül jelenik meg a rendszer fizikai elrendezésében). A processzorokat összekötő kommunikációs kapcsolatokat kötegekbe (bundles) rendezik, melyek a könyv lapjainak felelnek meg és veremként funkcionálnak: a processzorok egyikét egy új kommunikációs kapcsolat elejébe bekötve a korábbi kapcsolatokat a kötegben felfelé nyomjuk, a kapcsolat végébe egy processzort bekötve pedig a többit a kötegben lefelé nyomjuk. Az ilyen veremszerű működés miatt egyetlen köteg képes a kommunikációs kapcsolatok egy könyvbe ágyazási lap éleit alkotó halmazát kezelni. A kapcsolatok ilyen elrendezésével többfajta hálózati topológia megvalósítható, arra való tekintet nélkül, hogy melyik processzor fog meghibásodni, amíg elegendő nem hibás processzor marad a hálózat implementációjához. Az így implementálható hálózati topológiák pontosan azok, melyek könyvvastagsága nem haladja meg a rendelkezésre álló kötegek számát.[39] A könyvbe ágyazás használható a VLSI komponenseket az áramkör rétegeibe kötő vezetékek elhelyezésének modellezésére is.[49]

Veremrendezés

[szerkesztés]

A (Chung, Leighton & Rosenberg 1987) által említett másik alkalmazás a permutációk vermek segítségével történő sorba rakása volt. Donald Knuth (1968) nagy hatású eredménye volt, hogy megmutatta, hogy egy adatfolyamot feldolgozó rendszer, ami a bejövő elemeket egy verembe teszi, majd megfelelően kiválasztott időpillanatokban kiveszi onnan, pontosan akkor tudja sorba rendezni az adatokat, ha az eredeti rendet leíró permutációban nem szerepel a 231 permutációs mintázat.[50] Azóta sokan dolgoztak hasonló adatfolyam-rendezési feladatokon vermek és sorok általánosabb rendszereiben. A (Chung, Leighton & Rosenberg 1987) által leírt rendszerben a bemeneti adatfolyam minden elemét a több verem valamelyikében kell elhelyezni. Miután a bemeneti adatok minden elemét elhelyezték, a vermek tartalmát (megfelelő sorrendben) a kimeneti adatfolyamba teszik ki. Chung et al. megfigyelése szerint adott permutáció akkor rendezhető sorba ezzel a rendszerrel, ha a permutációból adott módon kinyert gráfnak létezik olyan könyvbe ágyazása, melynek csúcsai a könyv gerince mellett adott sorrendben helyezkednek el és a lapszám nem haladja meg a vermek számát.[39]

Forgalomszabályozás

[szerkesztés]
Egy útkereszteződés. Az áthaladó sávok közül a négy-négy bejövő, illetve kimenő, a két kijelölt kanyarodó sáv és a négy gyalogátkelőhely leírható egy könyvbe ágyazás gerincén helyet foglaló 14 csúcsként, ahol az élek a sávok közti összeköttetéseket jelképezik.

Ahogy (Kainen 1990) is leírta, a könyvbe ágyazás alkalmas lehet egy útkereszteződés közlekedési lámpái fázisainak leírására. Egy útkereszteződés forgalmi sávjai (beleértve a gyalogos átkelésre alkalmas, a kerékpáros és a gépjárművek számára fenntartott sávokat is) ábrázolhatók egy gráf csúcsaiként, egy könyvbe ágyazásban a könyv gerincén a kereszteződés óramutató járása szerinti sorrendjében elhelyezve. A bemenő sávokból a kimenő sávokba lehetséges útvonalak egy irányítatlan gráf éleiként reprezentálhatók. Például ennek az ábrának a gráfja tartalmazhat egy élt az ugyanazon útszegmenshez tartozó be- és kimenő sávok között, amennyiben az U-kanyar megengedett ebben az útkereszteződésben. Az élek egy adott részhalmaza akkor jelképezi az egymás zavarása nélkül bejárható útvonalakat, ha azok nem tartalmaznak a könyvbe ágyazás ugyanazon oldalán egymást metsző éleket. Tehát a gráf könyvbe ágyazása jelképezi a bejárható utak egymással nem interferáló részhalmazokra osztását, a gráf könyvvastagsága (a gerincbe való rögzített beágyazással) megadja a jelzőlámpák állapotainak minimális számát, ami ahhoz kell, hogy minden lehetséges forgalom áthaladjon a kereszteződésen.[51]

Gráfok lerajzolása

[szerkesztés]
A Goldner–Harary-gráf egy ívdiagramja. A síkba rajzolható ábra elkészítése érdekében a gráf két háromszögét szaggatott piros vonallal négybe vágták, így a gráf egy éle a vonal fölött és alatt is megjelenik.

A könyvbe ágyazást gyakran használják hálózati adatok vizualizációjára. A gráfok lerajzolása során alkalmazott két szokásos elrendezés, az ívdiagramok[52] és a körkörös elrendezések[53] is tekinthetők könyvbe ágyazásnak, amit felhasználnak a klaszterezett elrendezések,[44] a szimultán beágyazások[54] és a háromdimenziós gráfrajzolások elkészítése során is.[55]

Egy ívdiagram (arc diagram)[52] vagy lineáris beágyazás[42] a gráf csúcsait egy egyenes mentén helyezi el, a gráf éleit pedig a gráf alatt vagy fölött áthaladó félkörökként jeleníti meg, néha megengedve, hogy az él az egyenes egy szakaszán haladjon. Ez a rajzolási stílus olyan könyvbe ágyazásnak felel meg, amiben egy lap (ha minden félkör a vonal feletti) vagy két lap (ha a vonal mindkét oldalát kihasználják) található, és eredetileg gráfok metszési számának tanulmányozására találták ki.[56][57] A kétlapos könyvbe ágyazással nem rendelkező, de síkbarajzolható gráfok is ábrázolhatók ehhez hasonló módon, ha megengedjük, hogy az éleket a vonal alatt és fölött több félkör jelképezze. Az ilyen lerajzolás nem tekinthető definíció szerinti könyvbe ágyazásnak, ezért úgy szokták nevezni, hogy topologikus könyvbe ágyazás.[58] Minden síkbarajzolható gráf esetén lehetséges olyan beágyazást találni, melynek minden éle legfeljebb egyszer metszi a könyv gerincét.[59]

A Chvátal-gráf körkörös elrendezésben

A körkörös elrendezés egy másik rajzolási stílus, melyben a gráf csúcsai egy körön helyezkednek el és az élek vagy a körön kívül, vagy a körön belül húzódnak.[53] Az előzőekhez hasonlóan ha az élek a körön belül helyezkednek el (például egyenes szakaszokként), az egylapos könyvbe ágyazásnak felel meg, míg ha a kör belsejében és a körön kívül is vannak élek, az a kétlaposnak.[60]

Bármely stílus szerinti egylapos lerajzolásnál fontos a metszések számának minimalizálása, hogy csökkentsük a rajz vizuális bonyolultságát. A metszésszám minimalizálása NP-teljes,[42] de közelíthető O(log2 n) approximációs aránnyal, ahol n a csúcsok száma.[61] Az egy- vagy kétlapos metszési szám minimalizálása rögzített paraméter mellett kezelhető, ha a paraméter az adott gráf ciklomatikus száma, vagy a metszési szám és a faszélesség kombinációja.[62][63] Léteznek heurisztikus módszerek a metszési bonyolultság csökkentésére, amik például a csúcsok beszúrási sorrendjének óvatos megválasztásán és lokális optimalizáción alapulnak.[53]

A kétlapos, az élek rögzített lapokba osztásával történő könyvbe ágyazások értelmezhetők a klaszterezett síkba rajzolás (clustered planarity) példájaként, melynek során az adott gráfot úgy kell lerajzolni, hogy a gráf részei (az élek két részhalmaza) a klaszterezésnek megfelelően szerepeljenek a rajzon.[44] A kétlapos könyvbe ágyazások felhasználhatók gráfok szimultán beágyazásainak megkeresésére; ezeknél adott két, egymással megegyező csúcshalmazú gráf, és úgy kell elhelyezni a gráfokat, hogy mindkettő síkba rajzolható legyen egyenes szakaszú élekkel.[54]

A kettőnél több lapos könyvbe ágyazásokat használták háromdimenziós gráflerajzolások előállítására. (Wood 2002) olyan konstrukciót használt könyvbe ágyazáshoz, ami minden lapon minden csúcs fokszámát alacsonyan tartotta, hogy lehetséges legyen a gráfok háromdimenziós térbeli rácsba való alacsony térfogatú beágyazása.[55]

RNS-térszerkezet kialakítása

[szerkesztés]
Az emberi telomeráz egy pszeudocsomót tartalmazó részlete. Ha a részletet „kihúzzuk” egy könyvbe ágyazás gerince mentén, a kékkel jelölt bázispárok lerajzolhatók a gerinc fölötti és alatti, nem metsző részhalmazokként, így ez a pszeudocsomó bi-másodlagos szerkezetű.

Az RNS-molekulaszerkezet kihajtogatással való kialakulásának tanulmányozása során a nukleinsav másodlagos szerkezete sematikusan ábrázolható úgy, hogy egy bázisláncot (magát az RNS-szekvenciát) egy egyenes mentén lerajzolunk és az egyenes fölött ívekkel jelöljük a szerkezet bázispárjait. Tehát, bár az RNS bonyolult háromdimenziós szerkezettel rendelkezik, összekötöttségük (amikor a másodlagos szerkezet létezik) leírható egy absztrakt struktúrával, egy egylapos könyvbe ágyazással. Azonban nem minden RNS viselkedik ilyen egyszerű módon. (Haslinger & Stadler 1999) egyes RNS-pszeudocsomók leírására ún. „bi-másodlagos szerkezetet” (bi-secondary structure) javasolt, ami kétlapos könyvbe ágyazás formáját ölti: az RNS-szekvenciát itt is egy egyenes mentén írják le, de a bázispáros a vonal alatti és fölötti ívekként is megjelenhetnek. A bi-másodlagos szerkezet létezéséhez a gráf maximális fokszáma nem haladhatja meg a hármat: minden bázis a diagram legfeljebb egy ívében szerepelhet, plusz a bázisszekvenciában a két szomszédjához tartozó linkek. Ennek a leírásnak az előnye, hogy nem szerepelnek benne a ténylegesen térbeli csomók, de leírható vele a legtöbb ismert RNS-pszeudocsomó.[7]

Mivel ezen az alkalmazási területen a könyvgerinc menti rendezés előre ismert, adott bázispárok bi-másodlagos szerkezetének létezése egyszerűen tesztelhető. Az élek a két lapra történő kompatibilis elhelyezése megfogalmazható akár egy 2-SAT problémaként, akár azon húrmetszetgráf párossága teszteléseként, melyek csúcsai a bázispárokat, élei a bázispárok közti metszéseket írják le.[7] Egy alternatív és hatékonyabb megoldás, ahogy (Haslinger & Stadler 1999) is megmutatja, hogy egy bi-másodlagos szerkezet pontosan akkor létezik, ha a bemenet „diagramgráfja” (a bázispárok szekvenciasorrendje szerint körbe kötve a bázisokat és adott bázispárokat élekként hozzáadva) síkbarajzolható gráf.[7] Ezzel a karakterizációval a bi-másodlagos szerkezetek lineáris időben felismerhetők a síkgráfság tesztelése probléma egy példányaként.

(Blin et al. 2007) a másodlagos szerkezetek és a könyvbe ágyazások közötti összefüggést felhasználták az RNS másodlagos szerkezetek összehasonlítási problémái NP-nehézségének bizonyításában.[64] Amennyiben az RNS szerkezete harmadlagos és nem csak bi-másodlagos (tehát a diagramban kettőnél több lapot igényel), akkor a lapszám megállapítása megintcsak NP-nehéz.[65]

Számítási bonyolultságelmélet

[szerkesztés]

(Pavan, Tewari & Vinodchandran 2012) a könyvbe ágyazás felhasználásával tanulmányozták az irányított gráfok elérhetőségi problémájának számítási bonyolultságát. Megfigyeléseik szerint a két lapba ágyazható irányított gráfok elérhetőségi problémája egyértelmű logaritmikus tárban megoldható (az egyértelmű polinomiális (UP) polinom idejű problémák logaritmikus tárbeli bonyolultságra vonatkozó analógiája). Azonban a három lapba ágyazható irányított gráfok elérhetőségi problémájához a teljes logaritmikus tárral nemdeterminisztikusan megoldható bonyolultság szükséges. Ezért úgy tűnik, a könyvbe ágyazások szorosan kapcsolódnak ezzel a két bonyolultsági osztállyal.[66]

A konstans lapszámmal rendelkező expander gráfok létezése[36] a kulcslépés annak bizonyításában, hogy nem lehetséges kétszalagos nemdeterminisztikus Turing-gép szub-négyzetes idő alatti szimulációja egyszalagos nemdeterminisztikus Turing-géppel.[67]

A matematika más területei

[szerkesztés]

(McKenzie & Overbay 2010) a könyvvastagság absztrakt algebrabeli alkalmazásait vizsgálja, olyan gráfokkal, melyeket véges lokális gyűrűk zérusosztóiból definiál úgy, hogy minden zérusosztónak egy csúcs felel meg, az éleknek pedig az olyan értékpárosok, melyek szorzata nulla.[68]

Több publikációból álló sorozatában Dynnikov (Иван Алексеевич Дынников) a csomók és láncok topologikus könyvbe ágyazásait tanulmányozta, megmutatva, hogy ezek a beágyazások leírhatók szimbólumok kombinatorikus sorozataként és hogy két lánc topologikus ekvivalenciája demonstrálható beágyazásaik lokális megváltoztatásainak sorozataként.[69][70]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Book embedding című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

[szerkesztés]
  1. ↑ a b Persinger, C. A. (1966), "Subsets of n-books in E3", Pacific Journal of Mathematics 18: 169–173, DOI 10.2140/pjm.1966.18.169.
  2. ↑ a b Atneosen, Gail Adele (1968), On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. thesis, Michigan State University, p. 79, <http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6905835>. Lásd még Atneosen, Gail H. (1972), "One-dimensional n-leaved continua", Fundamenta Mathematicae 74 (1): 43–45, <http://matwbn.icm.edu.pl/ksiazki/fm/fm74/fm7415.pdf>.
  3. ↑ Kainen, Paul C. (1974), "Some recent results in topological graph theory", in Bari, Ruth A. & Harary, Frank, Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973), vol. 406, Lecture Notes in Mathematics, pp. 76–108.
  4. ↑ Ollmann, L. Taylor (1973), "On the book thicknesses of various graphs", in Hoffman, Frederick; Levow, Roy B. & Thomas, Robert S. D., Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. VIII, Congressus Numerantium, p. 459.
  5. ↑ a b c Yannakakis, Mihalis (1989), "Embedding planar graphs in four pages", Journal of Computer and System Sciences 38: 36–67, DOI 10.1016/0022-0000(89)90032-9
  6. ↑ a b c Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104–108, ISBN 0-89791-193-8, DOI 10.1145/12130.12141.
  7. ↑ a b c d e Haslinger, Christian & Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology 61 (3): 437–467, DOI 10.1006/bulm.1998.0085.
  8. ↑ Hales, T. C. (1997), "Sphere packings. II", Discrete and Computational Geometry 18 (2): 135–149, DOI 10.1007/PL00009312.
  9. ↑ A „gerinc” és „lap” (spine/pages) terminológia fordul elő a téma modern tárgyalásaiban. A „hát” és „levelek” (back/leaves) terminológiát lásd itt: (Persinger 1966).
  10. ↑ a b c d e f g Bernhart, Frank R. & Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B 27 (3): 320–331, DOI 10.1016/0095-8956(79)90021-2.
  11. ↑ Shahrokhi, Farhad; Székely, László A. & Sýkora, Ondrej et al. (1996), "The book crossing number of a graph", Journal of Graph Theory 21 (4): 413–424, DOI 10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5.
  12. ↑ a b c Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods 8 (2): 198–218, DOI 10.1137/0608018.
  13. ↑ Stöhr, Elena (1988), "A trade-off between page number and page width of book embeddings of graphs", Information and Computation 79 (2): 155–162, DOI 10.1016/0890-5401(88)90036-3.
  14. ↑ Stöhr, Elena (1991), "The pagewidth of trivalent planar graphs", Discrete Mathematics 89 (1): 43–49, DOI 10.1016/0012-365X(91)90398-L.
  15. ↑ a b c Enomoto, Hikoe & Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with O(M log N) crossings of edges over the spine", SIAM Journal on Discrete Mathematics 12 (3): 337–341, DOI 10.1137/S0895480195280319.
  16. ↑ a b c Blankenship, Robin & Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4358>.
  17. ↑ Enomoto, Hikoe; Miyauchi, Miki Shimabara & Ota, Katsuhiro (1999), "Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph", Discrete Applied Mathematics 92 (2-3): 149–155, DOI 10.1016/S0166-218X(99)00044-X.
  18. ↑ Ábrego, Bernardo M.; Aichholzer, Oswin & Fernández-Merchant, Silvia et al. (2012), "The 2-page crossing number of Kn (extended abstract)", Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12), ACM, New York, pp. 397–403, DOI 10.1145/2261250.2261310.
  19. ↑ A teljes páros gráfok könyvvastagságáról további eredményekhez lásd Enomoto, Hikoe; Nakamigawa, Tomoki & Ota, Katsuhiro (1997), "On the pagenumber of complete bipartite graphs", Journal of Combinatorial Theory, Series B 71 (1): 111–120, DOI 10.1006/jctb.1997.1773; de Klerk, Etienne; Pasechnik, Dmitrii V. & Salazar, Gelasio (2014), "Book drawings of complete bipartite graphs", Discrete Applied Mathematics 167: 80–93, DOI 10.1016/j.dam.2013.11.001.
  20. ↑ Sperfeld, Konrad (2013), "On the page number of complete odd-partite graphs", Discrete Mathematics 313 (17): 1689–1696, DOI 10.1016/j.disc.2013.04.028.
  21. ↑ Hasunuma, Toru & Shibata, Yukio (1997), "Embedding de Bruijn, Kautz and shuffle-exchange networks in books", Discrete Applied Mathematics 78 (1-3): 103–116, DOI 10.1016/S0166-218X(97)00009-7; Tanaka, Yuuki & Shibata, Yukio (2010), "On the pagenumber of the cube-connected cycles", Mathematics in Computer Science 3 (1): 109–117, DOI 10.1007/s11786-009-0012-y. See also Obrenić, Bojana (1993), "Embedding de Bruijn and shuffle-exchange graphs in five pages", SIAM Journal on Discrete Mathematics 6 (4): 642–654, DOI 10.1137/0406049.
  22. ↑ Bekos, Michael A.; Gronemann, Martin & Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science, pp. 137–148, DOI 10.4230/LIPIcs.STACS.2014.137.
  23. ↑ Heath, Lenny (1984), "Embedding planar graphs In seven pages", Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 74–83, DOI 10.1109/SFCS.1984.715903.
  24. ↑ Bekos, Michael A.; Kaufmann, Micheal & Klute, Fabian et al. (2020), Four Pages Are Indeed Necessary for Planar Graphs.
  25. ↑ a b c Dujmović, Vida & Wood, David R. (2007), "Graph treewidth and geometric thickness parameters", Discrete and Computational Geometry 37 (4): 641–670, DOI 10.1007/s00454-007-1318-7.
  26. ↑ a b c Eppstein, David (2001), Separating geometric thickness from book thickness.
  27. ↑ Wood, David (January 19, 2009), Book Thickness of Subdivisions, <http://www.openproblemgarden.org/op/book_thickness_of_subdivisions>. Hozzáférés ideje: 2013-02-05.
  28. ↑ Ganley, Joseph L. & Heath, Lenwood S. (2001), "The pagenumber of k-trees is O(k)", Discrete Applied Mathematics 109 (3): 215–221, DOI 10.1016/S0166-218X(00)00178-5.
  29. ↑ Malitz, Seth M. (1994), "Graphs with E edges have pagenumber O(√E)", Journal of Algorithms 17 (1): 71–84, DOI 10.1006/jagm.1994.1027.
  30. ↑ Malitz, Seth M. (1994), "Genus g graphs have pagenumber O(√g)", Journal of Algorithms 17 (1): 85–109, DOI 10.1006/jagm.1994.1028.
  31. ↑ a b c d Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Springer, pp. 321–328, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
  32. ↑ Blankenship, R. (2003), Book Embeddings of Graphs, Ph.D. thesis, Department of Mathematics, Louisiana State University. As cited by (Nešetřil & Ossona de Mendez 2012).
  33. ↑ Bekos, Michael A.; Bruckdorfer, Till & Kaufmann, Michael et al. (2015), "1-Planar graphs have constant book thickness", Algorithms – ESA 2015, vol. 9294, Lecture Notes in Computer Science, Springer, pp. 130–141, DOI 10.1007/978-3-662-48350-3_12.
  34. ↑ a b Bekos, Michael; Kaufmann, Michael & Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125.
  35. ↑ Barát, János; Matoušek, Jiří & Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics 13 (1): R3, <http://www.combinatorics.org/Volume_13/Abstracts/v13i1r3.html>.
  36. ↑ a b Dujmović, Vida; Sidiropoulos, Anastasios & Wood, David R. (2015), 3-Monotone Expanders, egy korábbi eredményt javítva, ami megmutatta a konstans lapszámú expanderek létezését: Bourgain, Jean (2009), "Expanders and dimensional expansion", Comptes Rendus Mathématique 347 (7-8): 357–362, DOI 10.1016/j.crma.2009.02.009; Bourgain, Jean & Yehudayoff, Amir (2013), "Expansion in SL2(ℝ) and monotone expanders", Geometric and Functional Analysis 23 (1): 1–41, DOI 10.1007/s00039-012-0200-9. Lásd még Galil, Zvi; Kannan, Ravi & Szemerédi, Endre (1989), "On 3-pushdown graphs with large separators", Combinatorica 9 (1): 9–19, DOI 10.1007/BF02122679; Dvir, Zeev & Wigderson, Avi (2010), "Monotone expanders: constructions and applications", Theory of Computing 6: 291–308, DOI 10.4086/toc.2010.v006a012.
  37. ↑ Heath, Lenwood S. & Rosenberg, Arnold L. (1992), "Laying out graphs using queues", SIAM Journal on Computing 21 (5): 927–958, DOI 10.1137/0221055.
  38. ↑ Dujmović, Vida & Wood, David R. (2004), "On linear layouts of graphs", Discrete Mathematics & Theoretical Computer Science 6 (2): 339–357.
  39. ↑ a b c Chung, Fan R. K.; Leighton, Frank Thompson & Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design", SIAM Journal on Algebraic and Discrete Methods 8 (1): 33–58, doi:10.1137/0608002, <http://www.math.ucsd.edu/~fan/mypaps/fanpap/fc82embedding.pdf>.
  40. ↑ Unger, Walter (1992), "The complexity of colouring circle graphs", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings, vol. 577, Lecture Notes in Computer Science, Berlin: Springer, pp. 389–400, DOI 10.1007/3-540-55210-3_199.
  41. ↑ Unger, Walter (1988), "On the k-colouring of circle-graphs", Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), vol. 294, Lecture Notes in Computer Science, Springer-Verlag, pp. 61–72, DOI 10.1007/BFb0035832.
  42. ↑ a b c d Masuda, Sumio; Nakajima, Kazuo & Kashiwabara, Toshinobu et al. (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers 39 (1): 124–127, DOI 10.1109/12.46286.
  43. ↑ Garey, M. R.; Johnson, D. S. & Miller, G. L. et al. (1980), "The complexity of coloring circular arcs and chords", SIAM Journal on Algebraic and Discrete Methods 1 (2): 216–227, DOI 10.1137/0601025.
  44. ↑ a b c Hong, Seok-Hee & Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (2009-004 ed.), Technical report, Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, <http://www-or.amp.i.kyoto-u.ac.jp/members/nag/Technical_report/TR2009-004.pdf> Archiválva 2020. szeptember 24-i dátummal a Wayback Machine-ben.
  45. ↑ Angelini, Patrizio; Di Bartolomeo, Marco & Di Battista, Giuseppe (2013), "Implementing a partitioned 2-page book embedding testing algorithm", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers, vol. 7704, Lecture Notes in Computer Science, Springer, pp. 79–89, DOI 10.1007/978-3-642-36763-2_8.
  46. ↑ (Nešetřil & Ossona de Mendez 2012), Corollary 18.1, p. 401.
  47. ↑ Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2008), "Grad and classes with bounded expansion. II. Algorithmic aspects", European Journal of Combinatorics 29 (3): 777–791, DOI 10.1016/j.ejc.2006.07.014.
  48. ↑ (Nešetřil & Ossona de Mendez 2012), Theorem 18.7, p. 405.
  49. ↑ Rosenberg, Arnold L. (1986), "Book embeddings and wafer-scale integration", Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), vol. 54, Congressus Numerantium, pp. 217–224.
  50. ↑ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, Section 2.2.1, Exercises 4 and 5, ISBN 0-201-89683-4, OCLC 155842391.
  51. ↑ Kainen, Paul C. (1990), "The book thickness of a graph. II", Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), vol. 71, Congressus Numerantium, pp. 127–132.
  52. ↑ a b Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110–116, DOI 10.1109/INFVIS.2002.1173155.
  53. ↑ a b c Baur, Michael & Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan, Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, vol. 3353, Lecture Notes in Computer Science, Springer, pp. 332–343, DOI 10.1007/978-3-540-30559-0_28.
  54. ↑ a b Angelini, Patrizio; Di Battista, Giuseppe & Frati, Fabrizio et al. (2012), "Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph", Journal of Discrete Algorithms 14: 150–172, DOI 10.1016/j.jda.2011.12.015.
  55. ↑ a b Wood, David R. (2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, vol. 2265, Lecture Notes in Computer Science, Springer, Berlin, pp. 312–327, DOI 10.1007/3-540-45848-4_25.
  56. ↑ Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proceedings of the National Academy of Sciences of the United States of America 52: 688–690, DOI 10.1073/pnas.52.3.688.
  57. ↑ Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network", Proceedings of the Institution of Electrical Engineers 115: 21–26, DOI 10.1049/piee.1968.0004.
  58. ↑ Miyauchi, Miki (2006), "Topological book embedding of bipartite graphs", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E89-A (5): 1223–1226, DOI 10.1093/ietfec/e89-a.5.1223.
  59. ↑ Giordano, Francesco; Liotta, Giuseppe & Mchedlidze, Tamara et al. (2007), "Computing upward topological book embeddings of upward planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007, Proceedings, vol. 4835, Lecture Notes in Computer Science, Springer, pp. 172–183, DOI 10.1007/978-3-540-77120-3_17.
  60. ↑ He, Hongmei & Sykora, Ondrej (2004), "New circular drawing algorithms", Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004, <https://dspace.lboro.ac.uk/2134/2386>.
  61. ↑ Shahrokhi, Farhad; Sýkora, Ondrej & Székely, László A. et al. (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, vol. 903, Lecture Notes in Computer Science, Springer, pp. 256–268, DOI 10.1007/3-540-59071-4_53.
  62. ↑ Bannister, Michael J.; Eppstein, David & Simons, Joseph A. (2013), "Fixed parameter tractability of crossing minimization of almost-trees", Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers, vol. 8242, Lecture Notes in Computer Science, pp. 340–351, DOI 10.1007/978-3-319-03841-4_30.
  63. ↑ Bannister, Michael J. & Eppstein, David (2014), "Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth", Proc. 22nd Int. Symp. Graph Drawing (GD 2014), vol. 8871, Lecture Notes in Computer Science, Springer-Verlag, pp. 210–221, DOI 10.1007/10.1007/978-3-662-45803-7_18.
  64. ↑ Blin, Guillaume; Fertin, Guillaume & Rusu, Irena et al. (2007), "Extending the hardness of RNA secondary structure comparison", Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers, vol. 4614, Lecture Notes in Computer Science, pp. 140–151, DOI 10.1007/978-3-540-74450-4_13.
  65. ↑ Clote, Peter; Dobrev, Stefan & Dotu, Ivan et al. (2012), "On the page number of RNA secondary structures with pseudoknots", Journal of Mathematical Biology 65 (6–7): 1337–1357, DOI 10.1007/s00285-011-0493-6.
  66. ↑ Pavan, A.; Tewari, Raghunath & Vinodchandran, N. V. (2012), "On the power of unambiguity in log-space", Computational Complexity 21 (4): 643–670, DOI 10.1007/s00037-012-0047-3.
  67. ↑ Galil, Zvi; Kannan, Ravi & Szemerédi, Endre (1989), "On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines", Journal of Computer and System Sciences 38 (1): 134–149, DOI 10.1016/0022-0000(89)90036-6.
  68. ↑ McKenzie, Thomas & Overbay, Shannon (2010), "Book embeddings and zero divisors", Ars Combinatoria 95: 55–63.
  69. ↑ Dynnikov, I. A. (1999), "Three-page approach to knot theory. Coding and local motions", Rossiĭskaya Akademiya Nauk 33 (4): 25–37, 96, DOI 10.1007/BF02467109.
  70. ↑ Dynnikov, I. A. (2001), "A new way to represent links, one-dimensional formalism and untangling technology", Acta Applicandae Mathematicae 69 (3): 243–283, DOI 10.1023/A:1014299416618.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Könyvbe_ágyazás&oldid=26467818”