Metódy kreslenia planárnych grafov

Základné definície :

Graf G=(V,E) je definovaný v učebnici Kvasnička-Pospíšil [KvPo08] pomocou množiny vrcholov V a množiny hrán E – neusporiadaných dvojíc e={u, v} vrcholov z V.

Orientovaný graf G=(V, E) je definovaný pomocou množiny vrcholov V a množiny E– usporiadaných dvojíc e=(u, v) vrcholov z V. Neorientovaný grafG=(V, E) je definovaný pomocou množiny vrcholov V a množiny E neorientovaných hrán, pričom každá hrana e ∈ E je reprezentovaná neusporiadanou dvojicou vrcholov z V.

Dva vrcholy u a v v neorientovanom grafe G sa volajú susedné v G, keď {u, v} je hrana grafu G. Keď e={u, v}, o hrane e sa hovorí, že je incidentná s vrcholmi u a v alebo spája vrcholy u a v. Stupeň vrcholu v neorientovanom grafe je rovný počtu hrán s ním incidentných. Vrchol stupňa 0 sa volá izolovaný, ak nie je spojený zo žiadnym iným vrcholom.

Cesta je sekvencia odlišných vrcholov v1, v2,. . . , vk, s k ≥ 2 spolu s hranami (v1, v2),. . . , (vk-1, vk). Dĺžka cesty je počet jej hrán. Cyklus je sekvencia odlišných vrcholov v1, v2,. . . , vk, s k ≥ 2, spoločne s hranami (v1, v2),. . . , (vk-1, vk), (vk, v1). Dĺžka cyklu je počet jeho vrcholov alebo počet jeho hrán.

Graf je súvislý, ak každé dva vrcholy sú spojené cestou. Nesúvislý graf je zjednotením dvoch alebo viac súvislých grafov, z ktorých žiaden pár nemá spoločný vrchol. Tieto súvislé podgrafy sa volajú kompakty grafu. Niekedy odstránením hrany alebo vrcholu z grafu sa graf rozpadne na viac komponentov.

Strom je súvislý graf bez cyklov. Koreňový strom T je súvislý strom s význačným vrcholom, ktorý nazývame koreň r.

Kresba (drawing) Γ grafu G, ako sa píše v [Tam13], priradí každému vrcholu v odlišný bod Γ (v) roviny, a každej hrane (u, v) jednoduchú otvorenú Jordanovu krivku Γ (u, v), s koncovými bodmi Γ (u) a Γ (v). Kresba je planárna, ak sa nepretínajú dve odlišné hrany, s výnimkou prípadných spoločných koncových bodov. Graf je planárny, ak pripúšťa planárnu kresbu. Planárna kresba rozdeľuje rovinu na spojité oblasti, ktoré nazývame plochy.

Podgraf grafu G=(V,E) je graf H=(W,F), kde W⊆ V a F ⊆E. Vzhľadom na dva grafy G1 (V1, E1) a G2 (V2, E2), ich zjednotenie G1 ∪ G2 je graf G (V1 ∪ V2, E1 ∪ E2). Analogicky ich prienik G1 ∩ G2 je graf G (V1 ∩ V2, E1 ∩ E2). Graf G2 je podgraf G1, ak G1 ∪ G2 = G1.

Vnorený graf je planárny graf s predšpecifikovanými typologickými vnoreniami (napr. množina stien), ktoré musia byť zakonzervované v grafe.

Neorientovaný graf G je súvislý, ak pre každú dvojicu uzlov u a v, G obsahuje cestu od u do v. Graf G s najmenej k+1 vrcholmi je k-súvislý, ak po odstránení k-1 vrcholov je G súvislý graf. Ekvivalentne, podľa [Tam13] je graf k-súvislý, „ak je k dispozícii k nezávislých ciest medzi každou dvojicou vrcholov“.

Graf G* = (V*, E*) nazývame duálny k planárnemu grafu G = (V, E), ak bol vytvorený nasledovným spôsobom: každá stena grafu G je reprezentovaná jedným vrcholom grafu G*. Cez každú hranu grafu G vedie práve jedna hrana grafu G* spájajúca vrcholy reprezentujúce steny po oboch stranách tejto hrany.

Vlastnosti kresieb :

Máme nekonečne veľa kresieb daného grafu [Nis04]. Keď kreslíme graf, radi by sme zvážili rôzne vlastnosti. V tejto časti predstavíme niektoré vlastnosti kreslenia grafov:

Oblasť. Kresba je zbytočná, ak je nečitateľná. Ak využitá oblasť kresby je veľká, musíme využiť veľa stránok, alebo znížiť rozlíšenie, čiže týmto spôsobom sa kresba stáva nečitateľnou. Preto je jedným z hlavných cieľov zabezpečiť malú oblasť. Malá oblasť kresby je tiež preferovaná v aplikačných doménach.

Pomer strán. Pomer strán je definovaný ako pomer dĺžky najdlhšej strany k dĺžke najkratšej strany najmenšieho obdĺžnika obklopujúceho kresbu.

Ohyby. Kresba s lomenými čiarami v ohybe niektorej z hrán mení smer, a preto ohyb na hrane zvyšuje zložitosť sledovania smeru hrany. Z tohto dôvodu, obe kritéria, celkový počet ohybov a počet ohybov na jednej hrane sa snažíme udržať čo najnižší.

Kríženia. Každé kríženie hrán nesie potenciál splynutia hrán, preto je snaha udržať počet krížení na minime.

Tvar plôch. Ak každá plocha kresby má pravidelný tvar, kresba vyzerá krajšie.

Symetria. Symetria je dôležité estetické kritérium pri kresbe grafov. Symetria dvoj-dimenzionálneho obrázku je izometria oblasti, ktorá fixuje obrázok. Poznáme dva druhy dvoj- dimenzionálnych symetrií a to rotačnú symetriu a reflexnú symetriu. Rotačná symetria je rotácia okolo bodu a reflexná symetria je reflexia na osi.

Uhlové rozlíšenie. Uhlové rozlíšenie sa mení vzhľadom na najmenší medzi dvoma priľahlými hranami v kresbe. Vyššie uhlové rozlíšenie je vhodné na zobrazovanie kresieb na rastrovom zariadení.

Vzory kreslenia grafov :

„Ako iste viete, neexistuje žiadny určitý spôsob, ako nakresliť graf a neexistuje žiaden algoritmus, ktorý by vždy nakreslil najkrajší graf“, hovorí sa v [Ger99]. Preto existuje niekoľko vzorov pre kreslenie grafov, ktoré opisujú základné kroky, ako nakresliť graf. Každý z týchto krokov potom môžeme nahradiť konkrétnymi algoritmami, ktoré majú odlišnú estetiku, alebo majú iné požadované vlastnosti.

1. Topológia – tvar – metrika

Tento prístup kreslenia grafov je trojúrovňové zdokonalenie počiatočného grafu. Tento prístup tiež zdôrazňuje minimalizáciu priesečníkov pri kreslení,pretože prvým krokom v postupe je planarizácia.

Tromi formami, ktoré sa použijú v tomto prístupe, sú topológia, tvar a metrika. Dve ortogonálne kresby majú rovnakú topológiu, ak je možné vnoriť jeden do druhého pomocou deformácie, pričom nie je narušené poradie vrcholov a hrán. Dve ortogonálne vykreslenia grafov majú rovnaký tvar, ak je možné vnoriť jeden do druhého zmenou dĺžky hrán, nie však uhlov, ktoré zvierajú hrany. Posledným vylepšením tohto prístupu je metrika. Dve ortogonálne kresby majú rovnakú metriku, ak je možné vnoriť jeden do druhého, iba posunutím a rotáciou.

Každá z hore uvedených foriem poskytuje popis kresby, ktorá zdokonaľuje predchádzajúcu. Konkrétne dve kresby s rovnakou metrikou majú rovnaký tvar, a taktiež dve kresby s rovnakým tvarom majú rovnakú topológiu.

Všeobecný postup pre prístup topológia – tvar – metrika spočíva v tom, že graf najskôr prechádza procesom planarizácie. V tomto kroku sa graf prevedie z jeho matematickej reprezentácie (napríklad V = {1, 2, 3, 4, 5, 6} a E = {(1,4), (1,5) (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)}) do 2D výkresu, kde je počet priesečníkov obmedzený na minimum. Ak v splanarizovanom grafe existujú priesečníky, sú nahradené fiktívnymi vrcholmi. Výstupom tohto procesu je prvá forma, topológia.

Po tom, ako graf splanarizujeme, pokračujeme procesom ortogonalizácie. V tomto kroku sú oblúky prerobené do pravých uhlov a vrcholy sú zarovnané. Výsledkom tohto kroku je forma, tvar.

toto je obrázok

Obrázok 1. [Ger99] Príkladom troch krokov v prístupe topológia - tvar - metrika. Prvým krokom je planarizácia a kríženie hrán je nahradené fiktívnym vrcholom. Pri druhom kroku sa graf stáva ortogonálnym a nakoniec je zhutnený do jeho konečnej podoby.

Posledným krokom tohto prístupu je zhustenie. Pri tomto procese sa fiktívne vrcholy odstránia a graf je upravený tak, aby zaberal minimálne množstvo plochy. Po tomto kroku má posledný graf formu, metrika.

2. Hierarchizácia

Hierarchický prístup je spôsob, ako vytvoriť hierarchie z orientovaných grafov. Prvý krok v hierarchickom prístupe je priradenie vrstiev. V tomto kroku sú vrcholom priradené vrstvy, ktoré začínajú v hornej časti a smerujú nadol. Každý vrchol je priradený vrstve Ln tak, že ak existuje hrana od u do v, a vrstva u je Li a vrstva v je Lj, potom i < j. Ak existuje medzera medzi vrstvami, napríklad keď hrana prechádza z L1 do L3, umiestni sa fiktívny vrchol na L2.

Po priradení vrstiev nasleduje proces redukcie križovania. V tomto kroku sa redukuje počet krížení hrán, aby graf vyzeral krajšie.

Posledný krok sa nazýva priradenie x-súradníc. V tomto štádiu sa všetkým bodom priradí pozícia, odstránia sa fiktívne vrcholy a všetky hrany sa vykreslia. V tomto kroku je možné zdôrazniť veľa rôznych estetických zmien, ako je minimalizácia ohybov alebo minimalizácia plochy.

toto je obrázok

Obrázok 2. Vyššie uvedený obrázok z [Ger99] je príkladom hierarchického prístupu v procese. Priradia sa vrstvy a vložia sa fiktívne vrcholy. Ďalej sa zníži počet krížení čiary a potom sa konečná podoba je bez fiktívnych vrcholov.

3. Viditeľnosť

Prístup viditeľnosti pre kreslenie grafov je všestranná všeobecne používaná technika na kreslenie nadväzujúcich úsečiek. Rovnako ako v prístupe topológia – tvar – metrika, prvým krokom v tomto prístupe je planarizácia. Opäť, mať tento proces ako prvý krok znamená, že prioritou je zníženie počtu krížení.

Krok viditeľnosti je v tomto prípade ťažké vysvetliť bez pohľadu na obrázok 3 nižšie. V podstate sa každý vrchol mení na vodorovnú čiaru, vrátane fiktívneho vrcholu. Všetky hrany sa potom nahradia vertikálnymi čiarami, ktoré spájajú vodorovné čiary.

Konečný diagram sa potom vytvorí po dokončení výmenného kroku. V tomto kroku sa horizontálne čiary nahradia jednotlivými bodmi a hrany sa ťahajú tak, aby tesne nasledovali zvislé čiary.

toto je obrázok

Obrázok 3. Vyššie uvedený obrázok z [Ger99] je príkladom prístupu viditeľnosti. Prvým krokom je planarizácia. Estetika minimalizácie plochy je zdôraznená vo fáze viditeľnosti a v záverečnom kroku môže byť zdôraznené množstvo rôznych estetík v závislosti od preferencie používateľa.

4. Augmentácia

Prístup augmentácie je podobný prístupu viditeľnosti v tom, že ide o general purpose graph drawing paradigm a jeho prvým krokom je planarizácia.

Druhý krok sa nazýva krok augmentácie. V tomto procese sa nakreslia falošné hrany v poradí s cieľom získať graf, v ktorom má každá plocha tri strany (maximálne rovinné). V nižšie uvedenom príklade vidíme, že na prvom obrázku má plocha {3,5,2,4} štyri strany. Po dokončení augmentačného kroku sa nakreslí falošná hrana {3,2}, čím sa vytvoria dve 3-stranné plochy {3,5,2} a {3,2,4}.

toto je obrázok

Obrázok 4. Opäť, tento prístup z [Ger99] zdôrazňuje minimalizovanie kríženia hrán, ale okrem tejto estetiky sa tiež snaží minimalizovať ohyby v dôsledku kroku priamych čiar k triangulácii.

V triangulačnom kroku sa nakreslí konečný graf pomocou geometrických vlastností trojuholníkov, vytvorených v predchádzajúcom kroku. Fiktívne vrcholy sú v tomto kroku odstránené a všetky hrany sú zmenené na priame čiary.

Štýly kresieb :

1. Planárne kresby:

Na obrázku 5 vidno planárnu kresbu a neplanárnu kresbu toho istého grafu. Je výhodnejšie nájsť planárnu kresbu grafu, ak má graf takúto vlastnosť. Samozrejme, nie každý graf má svoju planárnu kresbu.

toto je obrázok

Obrázok 5. (a) planárna kresba, a (b) neplanárna kresba toho istého grafu

Ak chceme nájsť planárnu kresbu zadaného grafu, ako prvé potrebujeme otestovať, či je daný graf planárny, alebo nie, píše sa v [Nis04]. Ak je planárny, potrebujeme nájsť planárne vnorenie nášho grafu, čo je dátová štruktúra reprezentujúca adekvátne zoznamy: v každom zozname hrany závislé od vrcholu sú usporiadané, buď všetky v smere chodu hodinových ručičiek, alebo proti tomuto smeru, vzhľadom na planárne vnorenie. Planárny graf s fixným planárnym vnorením je rovinný graf.

2. Kresby s lomenými hranami

Kresba s lomenými hranami je kresba daného grafu, v ktorej každá hrana tohto grafu je reprezentovaná polygonálnym reťazcom, [Nis04]. Tento typ kresby je zobrazený na obrázku 6. Bod, v ktorom hrana mení svoj smer v kresbe s lomenými čiarami, sa nazýva ohyb. Kresby s lomenými hranami sú užitočné na aproximáciu kresieb so zakrivenými hranami. Avšak nie je vhodné, aby na jednej hrane bolo viac ako dva alebo tri ohyby.

toto je obrázok

Obrázok 6. Kresba grafu s lomenými čiarami

3. Kresba s priamymi hranami

Kresba s priamymi hranami je kresba grafu, v ktorej každá hrana grafu je kreslená ako úsečka [Nis04], ako je ilustrované na obrázku 7 Kresba s priamymi čiarami je špeciálnym prípadom kresby s lomenými čiarami, kde hrany sú kreslené tak, aby neobsahovali žiadne ohyby. Wagner, Féry a Stein nezávisle na sebe dokázali, že každý planárny graf má svoju kresbu s priamymi hranami.

toto je obrázok

Obrázok 7. Kresba s priamymi hranami a aj konvexná kresba

4. Konvexná kresba

Kresba s rovnými čiarami rovinného grafu G sa nazýva konvexná kresba, ak hranice všetkých plôch G sú nakreslené ako konvexné polygóny (všetky vnútorné uhly sú menšie ako 180°) [Nis04], ako môžete vidieť na obrázku 7 Avšak nie každý rovinný graf sa dá upraviť na konvexnú kresbu, iba každý 3- súvislý rovinný graf má takýto typ kresby.

5. Ortogonálna kresba

Ortogonálna kresba je kresba rovinného grafu, v ktorej je každá hrana nakreslená ako reťazec vodorovných a zvislých úsečiek [Nis04], ako je ilustrované na obrázku 8(a). Ortogonálne kresby priťahujú veľa pozornosti vďaka ich početným aplikáciám napríklad v databázových diagramoch. Ortogonálna kresba sa nazýva oktagonálnou, ak každý vonkajší cyklus je vykreslený ako obdĺžnik a každá vnútorná plocha je vykreslená ako priamkový polygón s najviac ôsmymi rohmi. Obrázok 8(c)

toto je obrázok toto je obrázok

Obrázok 8. (a) ortogonálna kresba, (b) krabicovo-ortogonálna kresba, (c) oktagonálna kresba z [Nis04]

6. Krabicovo-ortogonálna kresba

Formálne každý vrchol v ortogonálnej kresbe je vykreslený ako bod [Nis04], ako na obrázku 8(a). Očividne graf, ktorého vrchol je stupňa päť a viac, nemá ortogonálnu kresbu. Krabicovo-ortogonálna kresba grafu má každý vrchol vykreslený ako obdĺžnik, ktorý nazývame krabica a každá hrana je vykreslená ako postupnosť striedajúcich sa vodorovných a zvislých úsečiek, ako je ilustrované na obrázku 8(b). Každý rovinný graf sa dá upraviť na krabicovo-ortogonálnu kresbu.

7. Obdĺžniková kresba

Obdĺžniková kresba rovinného grafu G je kresba G, v ktorej všetky vrcholy sú vykreslené ako vrcholy, každá hrana je vykreslená ako vodorovná alebo zvislá úsečka bez kríženia hrán a každá plocha je vykreslená ako obdĺžnik [Nis04], ako na obrázku 9(a). Vieme, že nie každý rovinný graf má obdĺžnikovú kresbu. Thomassen a Rahman vyslovili nutné a postačujúce podmienky na to, aby mal rovinný graf obdĺžnikovú kresbu, ktoré hovoria, že graf musí byť maximálne stupňa tri.

toto je obrázok

Obrázok 9. (a) obdĺžniková kresba a (b) krabicovo-obdĺžniková kresba

8. Krabicovo-obdĺžniková kresba

Krabicovo-obdĺžniková kresba rovinného grafu je taká kresba G v rovine, že každý vrchol je vykreslený ako obdĺžnik, ktorý voláme krabica a obrys každej plochy je vykreslený ako obdĺžnik [Nis04], ako je ilustrované na obrázku 9(b). Ak G má viacero hrán alebo vrcholov stupňa päť a viac, potom G nemá obdĺžnikovú kresbu, ale môže mať krabicovo-obdĺžnikovú kresbu. Avšak nie každá rovinná kresba má krabicovo-obdĺžnikovú kresbu.

9. Mriežková kresba

Kresba grafu, v ktorej sú vrcholy a ohyby umiestnené na bodoch v mriežke [Nis04], ako je ilustrované na obrázku 10, sa nazýva mriežková kresba. Prístup mriežkových kresieb prekoná nasledujúce problémy pri kreslení grafov, ktoré vznikajú v dôsledku práce s reálnymi číslami.

a) Keď vnorenie má byť vykreslené na rastrovom zariadení, reálne súradnice vrcholu treba zmeniť na celočíselné mriežkové body, pričom nie je zaručené, že po zaokrúhľovaní sa dosiahne správne vnorenie.

b) Veľa vrcholov môže byť koncentrovaných na malom priestore našej kresby. Teda vnorenie môže byť chaotické a priesečníky čiar nemusia byť zachytené.

c) Nie je možné porovnať požadovanú oblasť pre dve alebo viac rôznych výkresov pomocou reálnej aritmetiky, pretože akákoľvek kresba sa nemusí hodiť na malú oblasť použitím zväčšenia.

toto je obrázok

Obrázok 10. (a) mriežková kresba s rovnými čiarami, (b) obdĺžniková mriežková kresba

10. Kresba viditeľnosti

Kresba viditeľnosti (visibility drawing) rovinného grafu G je kresba, kde každý vrchol je vykreslený ako vodorovná úsečka a každá hrana je vykreslená ako zvislá úsečka [Nis04]. Zvislá úsečka reprezentujúca hranu musí spájať body na vodorovných útvaroch, ktoré reprezentujú koncové vrcholy. Obrázok 11(b) znázorňuje kresbu viditeľnosti rovinného grafu G na obrázku 11(a).

2-viditeľná kresba je zovšeobecnením viditeľnej kresby, kde vrcholy sú vykreslené ako krabice a hrany sú vykreslené buď ako vodorovné alebo zvislé úsečky. Na obrázku 11(c) môžeme vidieť 2-viditeľnú kresbu rovinného grafu na obrázku 11(a).

toto je obrázok toto je obrázok

Obrázok 11. (a) rovinný graf G, (b) kresba viditeľnosti G, (c) 2-viditeľná kresba G