11   Pokročilé kreslení grafů
Tato lekce se soustřeďuje na následující otázku: Jak vhodně nakreslíme nerovinný graf? Ukážeme si dva různé pohledy.
Jednak mimo tradičního kreslení grafů „na papír", tj. do roviny, si lze představit kreslení grafů na složitější povrchy (plochy), třeba na povrch duše pneumatiky. Co nám takovéto rozšířené kreslení grafů přinese nového?
Nebo zůstaneme v rovině, ale povolíme křížení hran a budeme hledat „esteticky pěkná" nakreslení, či dokonce jiné modely jako rovinná pokrytí. □
Stručný přehled lekce
• 0 „vyšších" plochách, orientovatelné a neorientovatelné plochy.
• Kreslení grafů na plochy, popis nakreslení, Eulerův vztah.
• Grafy na plochách a zakázané minory.
• Průsečíkové číslo grafu, základní definice a fakta.
• Zlehka o kuriózním problému rovinného pokrytí.
11.1   Co jsou to plochy
Nejprve si stručně uvedeme důležitý výsledek klasické topologie - klasifikaci ploch. Věta 11.1. Každá plocha (tj. kompaktní 2-manifold bez hranice) je homeomorfní
- So sféře,
- S h sféře s h přidanýma „ušima" (handle),
- N k sféře s k přidanými „křížícími místy" (crosscap).
Přidávání uší na sféru je snadno představitelná konstrukce (viz následující ilustrace nalevo). Avšak crosscap je velmi obtížné vizualizovat v Euklidovské geometrii, takže pro ilustraci si jej téměř ekvivalentně můžeme nahradit připojováním Mobiova proužku (viz ilustrace napravo) k hranici polosféry.
□
Definice: Crosscap na ploše je kružnice, jejíž protilehlé dvojice bodů jsou ztotožněny (vnitřek kruhu přitom ploše už nepatří).
Značení: Plocha S± je známý torus (ilustrace následující vlevo), neboli povrch duše kola.
Plocha 7Vi je projektivní rovina a vypuštěním kruhu z 7Vi vzniká zmíněný Móbiův proužek.
Plocha 7V2 je tzv. Kleinova láhev (ilustrace vpravo), jejímž podélným rozříznutím vzniknou dva Mobiovy proužky.
□
Plochy So a Sh jsou orientovatelné, kdežto M k jsou neorientovatelné. □
Co za plochu však vzniká kombinovaným přidáváním uší a crosscapů? Na to je snadná odpověď, vzniknou jen znovu už výše popsané plochy.
Lema 11.2. Máme-li plochu £ vzniklou ze sféry přidáním k > 2 crosscapů a h uší, tak E je homeomorfní ploše vzniklé ze sféry přidáním k — 2 crosscapů a h + 1 uší.
Značení: Klasická topologie používa následující způsob reprezentace vyšších ploch -plocha je zobrazena jako pravidelný mnohoúhelník, jehož strany jsou v naznačených orientacích po dvojicích ztotožněny.
Například ztotožněním protilehlých dvojic stran čtverce v naznačených směrech vznikají (zleva) projektivní rovina a torus.
Mi Si
11.2   Kreslení grafů na plochy
Definice 11.3. Nakreslením grafu G na plochu E
myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body na E a hrany jako oblouky spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. □
Na vyšší plochy přenášíme i další pojmy rovinného kreslení, jako pojem stěny.
Definice: Nakreslení grafu G na plochu E je buňkové, pokud je každá jeho stěna (bez své hranice) homeomorfní otevřenému disku. □
Fakt: Buňkové nakreslení 2-souvislého grafu G je jednoznačně určeno svými stěnovými kružnicemi a jako takové definuje i plochu E až na homeomorfismus.
(Neboli plochu E lze „slepit" z jednotlivých disků stěn podél společných hran u stěn.)n
Tvrzení 11.4. Buňkové nakreslení grafu G na orientovatelnou plochu E je jednoznačně určeno rotačním schématem vycházejících hran u svých vrcholů.
Rotační schéma u každého vrcholu v nakreslení určuje cyklické pořadí hran (v globálně zvolené orientaci) vycházejících z tohoto vrcholu v našem nakreslení.
Kreslení na určenou plochu
Tvrzení 11.5. Do projektivní roviny lze bez krížení hran nakreslit úplné grafy K$ i K§, na torus také K-j, kdežto na Kleinovu láhev K-j nakreslit nelze.
Mnohé poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Z těch jednoduchých je nejdůležitější Eulerův vztah (Věta 8.2).
Věta 11.6. Nechí buňkové nakreslení souvislého grafu G na ploše £ má f stěn. Pak
\V(G)\+f-\E(G)\=X&)., kde        (Eulerova charakteristika plochy) je 2 — 2h pro £ — S h a 2 — k pro E — AÍjjj
Z Eulerova vztahu vyplývají důležitá omezení na maximální počet hran - jednoduchý n-vrcholový graf nakreslený na toru nebo Kleinově láhvi nemůže mít více než 3n hran.
11.3   Překážky kreslení na plochy
Podle Věty 8.5 lze rovinnost zadaného grafu poměrně rychle algoritmicky rozhodnout i najít nakreslení. I tento silný výsledek má stejně silné zobecnění na vyšší plochy (Mohar), ale už bohužel není vhodný pro praktické implementace.
Věta 11.7. Pro každou pevnou plochu T existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na T, nebo určí minimální překážku nakres-litelnosti na T,, n
Poznámka: Za zmínku stojí fakt, že obecnější problém určit nejjednodušší plochu, na kterou lze daný graf nakreslit, je už A/"?3-těžký.
Z jiné strany lze zobecňovat Kuratowského Větu 8.8 na vyšší plochy.
Fakt: Vlastnost grafu být nakreslitelný na určenou plochu se zachovává pro všechny jeho podgrafy i minory. □
Třebaže je známo, že zobecnění Kuratowského věty s konečným počtem překážek je platné pro každou plochu, konkrétní seznam zakázaných minorů či podrozdělení známe pouze u jediné vyšší plochy (Archdeacon):
Věta 11.8. GrafG je nakreslitelný do projektivní roviny, právě když neobsahuje žádný minor isomorfní některému z následujících 35 grafů.
Význam grafů na plochách
Původní motivace výzkumu kreslení grafů na plochy je přirozená - byla to především snaha o řešení problému čtyř barev. Nyní však již máme Větu o čtyřech barvách, takže co dále motivuje výzkum kreslení grafů na vyšší plochy, mimo „pěkných obrázků"?
S grafy nakreslenými na plochách se setkáme ve dvou základních teoretických oblastech:
• Algebraické - studium pravidelných „map" na plochách. □
• Strukturální grafové - celá Robertson-Seymourova teorie grafových minorů, třebaže na první pohled s kreslením grafů nemá nic společného, stojí na grafech nakreslených na plochách. □
Abychom si poslední poněkud překvapivý poznatek blíže vysvětlili, uvedeme si stručně následující asi nejdůležitější mezivýsledek Robertson-Seymourovy teorie.
Věta 11.9. Mějme nerovinný graf H. Pak každý graf G, který neobsahuje minor isomorfní H, má stromovou dekompozici (Definice 10.4) následující vlastnosti:
Každý její balík (bez ohledu na velikost) indukuje podgraf který je až na omezeně mnoho „lokálních výjimek" nakreslitelný na nějakou plochu £ takovou, že H na £ nakreslit nelze.
11.4   O průsečíkovém čísle grafů
Mimo Definici 11.3 je přirozené uvažovat ještě jedno zobecnění rovinných nakreslení: Jak přistupovat k hezkým kreslením nerovinných grafů do roviny?
Definice 11.10. Obecným nakreslením grafu G do roviny
(viz také Definice 8.1) rozumíme zobrazení, ve kterém jsou vrcholům G přiřazeny různé body roviny a hranám jednoduché křivky spojující koncové vrcholy. □
Přitom je požadováno,
- aby se žádné tři hrany neprotínaly v jednom bodě (jiném než koncový vrchol), □
- aby žádná hrana neprocházela jiným vrcholem □
- a aby se každá protínající se dvojice hran „křížila" (ne jednostr. dotyk).
Petr Hliněný,  Fl MU Brno, 2013
10/18
Fl: MA010: Kreslení grafů
Příklad 11.11. Podívejme se na následující tři (obecná) nakreslení do roviny. Jsou všechna „optimální", tj. je počet jejich křížení nejmenší možný?
Snadno vidíme, že prvnígraf lze nakreslit i bez kríženia druhý graf jen s jedním křížením. Naopak třetí graf už s méně kříženími nakreslit nelze. Uměli byste toto dokázat? □ C
Definice: Průsečíkové číslo grafu G v rovině je definováno jako nejmenší možný počet křížení dvojic hran přes všechna nakreslení G do roviny. Značíme cr(G).
Proč se o průsečíkové číslo zajímáme?
V dnešní době je problém průsečíkového čísla velmi důležitý v praktických oblastech VLSI designu (Leighton) a „lidsky čitelné" vizualizace grafů v různých schématech.
Petr Hliněný,  Fl MU Brno, 2013
11/18
Fl: MA010: Kreslení grafů
Příklad 11.12. Určeme průsečíková čísla následujících dvou grafů:
Odpověd 2 a 3. □ C
Ač prozatím může studovaná problematika vypadat jako hříčka či hračka, ve skutečnosti se jedná o nezvykle obtížný grafový problém. To ostatně nejlépe ilustruje už následující:
Fakt: Přesné obecné hodnoty průsečíkových čísel nejsou známy ani pro úplné či úplné bipartitní grafy!
Petr Hliněný,  Fl MU Brno, 2013
12/18
Fl: MA010: Kreslení grafů
Výpočetní složitost průsečíkového čísla
Věta 11.13. Problém určit, zda průsečíkové číslo cr(G) < k pro G a k na vstupu je NT-úplný. Toto platí i když G je kubický 3-souvislý graf.
Dokonce je-li dán rovinný graf G a dvojice jeho nespojených vrcholů u,v, tak problém určit pro k na vstupu, zda průsečíkové číslo cr(G + uv) < k, je MV-úplný.
Zamyslete se sami, proč by problém průsečíkového čísla měl vůbec náležet do třídy MV, není to tak zřejmé... □
V praxi se ukazuje, že určení průsečíkového čísla je přímo zoufale těžký problém, ještě mnohem beznadějnější než třeba zjištění barevnosti. Snad jediným existujícím „pozitivním" (i když zcela nepraktickým) přesným algoritmickým výsledkem je následující:
Věta 11.14. Pro fixní k lze otestovat, zda cr(G) < k, v lineárním čase vzhledem k počtu vrcholů grafu (závislost na parametru k je však doslova „brutální"). □
Další existující pozitivní algoritmické výsledky se pak týkají už jen aproximací průsečíkového čísla nebo výpočtů pro konkrétní malé grafy (řádově v desítkách vrcholů).
Petr Hliněný,  Fl MU Brno, 2013
13/18
Fl: MA010: Kreslení grafů
11.5   O problému rovinného pokrytí
Na závěr si jako kuriozitu uvedeme zajímavý, třebaže okrajový, problém známý od 80-tých let pod názvem Negamiho hypotéza planárních pokrytí nebo Negamiho 12 oc hypotéza. Avšak k velmi podobné otázce nezávisle ve stejné době dospěl i Fellows. Problém je hezký především svou „chytlavostí" a jednoduchostí zadání.
Definice: Říkáme, že graf H pokrývá graf G, pokud existuje surjektivní zobrazení t : V (H) —>• V (G) takové, že sousedé každého vrcholu v grafu H jsou bijektivně zobrazeny na sousedy vrcholu t (v) grafu G.
H
G
Petr Hliněný,  Fl MU Brno, 2013
14/18
Fl: MA010: Kreslení grafů
Negamiho hypotéza rovinných pokrytí
Hypotéza 11.15. Souvislý graf G má pokrytí (nějakým) konečným rovinným grafem, právě když G samotný je nakreslitelný do projektivní roviny.
Zde je příklad dvojitého pokrytí grafu K$ rovinným grafem o 10 vrcholech.
H
Fakt: Je-li G nakreslitelný do projektivní roviny, pak univerzální pokrytí projektivní roviny sférou okamžitě dá nakreslení dvojitého rovinného pokrytí grafu G.
Petr Hliněný,  Fl MU Brno, 2013
15/18
Fl: MA010: Kreslení grafů
Letna 11.16. K důkazu Hypotézy 11.15 stačí ověřit, že žádný z 32 souvislých zakázaných minorů z Věty 11.8 nemá konečné rovinné pokrytí.
Kupodivu pro většinu z oněch 32 grafů to lze dokázat velmi snadno. Další výsledky, na kterých se podíleli Archdeacon, Fellows, Negami, Thomas a autor, vedly k dále uvedeným poznatkům, které jsou tím nejsilnějším, co o řešení Negamiho hypotézy víme.
Věta 11.17. Pokud graf Ki 2,2,2 nemá kon. rov. pokrytí, je Hypotéza 11.15 pravdivá.
Věta 11.18. Existuje jen 16 následujících konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.15 mohla být nepravdivá.
Petr Hliněný,  Fl MU Brno, 2013
16/18
Fl: MA010: Kreslení grafů
O rovinných emulátorech
Mírnou modifikací konceptu planárního pokrytí představuje tato definice, podaná Fel-lowsem nezávisle na Negamim.
Definice: Říkáme, že graf H je emulátorem grafu G, pokud existuje surjektivní zobrazení t : V (H) —>• V (G) takové, že sousedé každého vrcholu v grafu H jsou surjek-tivně zobrazeny na sousedy vrcholu t (v) grafu G. □
Na rozdíl od rovinných pokrytí mohou mít emulátory poměrně bohatší strukturu, přesněji řečeno sousedé mohou být "duplikováni", viz tento příklad emulátoru trojúhelníka:
c2 &2
Petr Hliněný,  Fl MU Brno, 2013
17/18
Fl: MA010: Kreslení grafů
Jelikož je na první pohled z definice "jasné" , že duplikace sousedů nemůže být přínosná pro existenci planárních emulátorů (ve srovnání s pokrytími), již Fellows vyslovil domněnku, že souvislý graf má konečné rovinné pokrytí právě tehdy, když má konečný rovinný emulátor.   Přesto se na závěr roku 2008 objevilo skutečné překvapení:
Věta 11.19. (Rieck a Yamashita) Existuje graf, který není projektivní a nemá konečné rovinné pokrytí a přesto má konečný rovinný emulátor.
1 4
3 2
Problematika, které grafy mají konečné rovinné emulátory, je stále široce otevřená.
Petr Hliněný,  Fl MU Brno, 2013
18/18
Fl: MA010: Kreslení grafů