11-planar/11-planar.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{11}{Kreslení grafů do roviny}{}
   4
   5 Rovinné grafy se objevují v~nejrůznějších praktických aplikacích teorie grafů,
   6 a~tak okolo nich vyrostlo značné množství algoritmů. I~když existují výjimky,
   7 jako například již zmíněné hledání kostry rovinného grafu, většina takových
   8 algoritmů pracuje s~konkrétním vnořením grafu do~roviny (rovinným nakreslením).
   9
  10 Proto se zaměříme na~algoritmus, který zadaný graf buďto vnoří do~roviny, nebo se
  11 zastaví s~tím, že graf není rovinný. Tarjan již v~roce 1974 ukázal \cite{tarjan:planarity},
  12 že je to možné provést v~lineárním čase, ale jeho algoritmus je poněkud
  13 komplikovaný. Od~té doby se objevilo mnoho zjednodušení, prozatím vrcholících
  14 algoritmem Boyera a Myrvoldové \cite{boyer:cutting}, a ten zde ukážeme.
  15
  16 Zmiňme ještě, že existují i algoritmy, které vytvářejí rovinná nakreslení s~různými
  17 speciálními vlastnostmi. Je to například Schnyderův algoritmus~\cite{schnyder:grid}
  18 generující v~lineárním čase nakreslení, v~němž jsou hrany úsečkami a vrcholy
  19 leží v~mřížových bodech mřížky $(n-2)\times (n-2)$, a~o~něco jednodušší algoritmus
  20 Chrobaka a Payneho \cite{chrobak:grid} kreslící do~mřížky $(2n-4)\times (n-2)$.
  21 Oba ovšem pracují tak, že vyjdou z~obyčejného rovinného nakreslení a upravují ho,
  22 aby splňovalo dodatečné podmínky.
  23
  24 \h{DFS a bloky}
  25
  26 Připomeňme si nejprve některé vlastnosti prohledávání do~hloubky (DFS) a jeho použití
  27 k~hledání komponent vrcholové 2-souvislosti {\I (bloků).}
  28
  29 \s{Definice:} Prohledávání orientovaného grafu do~hloubky rozdělí hrany do~čtyř druhů:
  30 \itemize\ibull
  31 \:{\I stromové} -- po~nich DFS prošlo a rekurzivně se zavolalo; tyto hrany
  32 vytvářejí {\I DFS strom} orientovaný z~kořene;
  33 \:{\I zpětné} -- vedou do~vrcholu, který leží na cestě z~kořene DFS stromu
  34 do právě prohledávaného vrcholu; jinými slovy vedou do vrcholu, který se
  35 právě nachází na~zásobníku;
  36 \:{\I dopředné} -- vedou do~již zpracovaného vrcholu ležícího v~DFS stromu pod aktuálním vrcholem;
  37 \:{\I příčné} -- zbývající hrany, které vedou do vrcholu již zpracovaného vrcholu
  38 v~jiném podstromu.
  39 \endlist
  40
  41 \s{Pozorování:}
  42 Pokud DFS spustíme na neorientovaný graf a hranu, po~níž jsme už jednou prošli,
  43 v~opačném směru ignorujeme, existují pouze stromové a zpětné hrany. DFS strom
  44 tvoří kostru grafu.
  45
  46 Nyní už se zaměříme pouze na~neorientované grafy~\dots
  47
  48 \s{Lemma:} Relace \uv{Hrany $e$ a $f$ leží na~společné kružnici} (značíme $e\sim f$) je ekvivalence. Její
  49 třídy tvoří maximální 2-souvislé podgrafy (bloky); ekvivalenční třídy s~jedinou hranou (mosty) považujeme
  50 za triviální bloky. Vrchol $v$ je artikulace právě tehdy, sousedí-li s~ním hrany z~více bloků.
  51
  52 Pokud spustíme na~graf DFS, je přirozené testovat, do~jakých bloků patří stromové
  53 hrany sousedící s~právě prohledávaným vrcholem~$v$: stromová hrana $uv$, po~které jsme
  54 do~$v$ přišli, a hrany $vw_1$ až $vw_k$ vedoucí do~podstromů $T_1$ až $T_k$ (zpětné hrany
  55 jsou vždy ekvivalentní s~hranou $uv$). Pokud je $uv \sim vw_i$, musí existovat cesta
  56 z~podstromu $T_i$ do~vrcholu~$u$, která nepoužije právě testované hrany. Taková cesta
  57 ale může podstrom opustit pouze zpětnou hranou (stromová je zakázaná a dopředné ani příčné
  58 neexistují). Jinými slovy $uv\sim vw_i$ právě tehdy, když existuje zpětná hrana z~podstromu~$T_i$
  59 do~vrcholu $u$ nebo blíže ke~kořeni.
  60
  61 Pokud některá dvojice $vw_i$, $vw_j$ není ekvivalentní přes hranu $uv$ (nebo pokud hrana $uv$
  62 ani neexistuje, což se nám v~kořeni DFS stromu může stát), leží tyto hrany v~různých blocích, protože
  63 $T_i$ a $T_j$ mohou být spojeny jen přes své kořeny (příčné hrany neexistují). Ze~zpětných
  64 hran tedy získáme kompletní strukturu bloků.
  65
  66 Nyní si stačí rozmyslet, jak existenci zpětných hran testovat rychle. K~tomu se bude hodit:
  67
  68 \s{Definice:} Je-li $v$ vrchol grafu, pak:
  69 \itemize\ibull
  70 \:$\<Enter>(v)$ udává pořadí, v~němž DFS do~vrcholu~$v$ vstoupilo.
  71 \:$\<Ancestor>(v)$ je nejmenší z~\<Enter>ů vrcholů, do~nichž vede z~$v$ zpětná hrana,
  72 nebo $+\infty$, pokud z~$v$ žádná zpětná hrana nevede.
  73 \:$\<LowPoint>(v)$ je minimum z~\<Ancestor>ů vrcholů ležících v~podstromu pod~$v$, včetně $v$ samého.
  74 \endlist
  75
  76 \s{Pozorování:} \<Enter>, \<Ancestor> i \<LowPoint> všech vrcholů lze spočítat
  77 během prohledávání, tedy také v~lineárním čase.
  78
  79 Rozpoznávání bloků a artikulací můžeme shrnout do~následujícího lemmatu:
  80
  81 \s{Lemma:} Pokud $v$ je vrchol grafu, $u$ jeho otec a $w$ jeho syn v~DFS stromu,
  82 pak stromové hrany $uv$ a $vw$ leží v~tomtéž bloku ($uv\sim vw$) právě
  83 tehdy, když $\<LowPoint>(w) < \<Enter>(v)$, a~$v$ je artikulace právě když
  84 některý z~jeho synů $w$ má $\<LowPoint>(w) \ge \<Enter>(v)$.
  85 Kořen DFS stromu je artikulace, právě když má více než jednoho syna.
  86
  87 \h{Postup kreslení}
  88
  89 Graf budeme kreslit v~opačném pořadí oproti DFS, tj. od~největších \<Enter>ů k~nejmenším,
  90 a vždy si budeme udržovat blokovou strukturu již nakreslené části grafu, uspořádanou
  91 podle DFS stromu -- každý blok bude mít svůj kořen, s~výjimkou nejvyššího bloku
  92 je tento kořen současně artikulací v~nadřazeném bloku. Aby se nám tato situace snadno
  93 reprezentovala, artikulace naklonujeme a každý blok dostane svou vlastní kopii artikulace.
  94
  95 Také budeme využívat toho, že nakreslení každého bloku, který není
  96 most, je ohraničeno kružnicí, a mosty zdvojíme, aby to pro ně platilo
  97 také. Navíc v~libovolném nakreslení můžeme kterýkoliv blok spolu se všemi bloky
  98 ležícími pod~ním překlopit podle kořenové artikulace, aniž bychom porušili
  99 rovinnost.
 100
 101 \finalfix{
 102 \smallskip
 103 \figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{}
 104 \figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{}
 105 }
 106
 107 Všimněme si, že pokud vede z~nějakého už nakresleného vrcholu ještě nenakreslená hrana,
 108 lze pokračovat po~nenakreslených hranách až do~kořene DFS stromu. Všechny vrcholy, ke~kterým
 109 ještě bude potřeba něco připojit (takovým budeme říkat {\I externí} a hranám
 110 rovněž; za~chvíli to nadefinujeme formálně), proto musí ležet v~téže stěně dosud nakresleného
 111 podgrafu a bez újmy na~obecnosti si vybereme, že to bude vnější stěna.
 112
 113 Základním krokem algoritmu tedy bude rozšířit nakreslení o~nový
 114 vrchol~$v$ a o~všechny hrany vedoucí z~něj do~jeho (již nakreslených)
 115 DFS-následníků.  Stromové hrany půjdou nakreslit vždy, přidáme je jako
 116 triviální bloky (2-cykly) a nejsou-li to mosty, brzy se nějakou
 117 zpětnou hranou spojí s~jinými bloky. Zpětné hrany byly až donedávna
 118 externí, takže přidání jedné zpětné hrany nahradí cestu
 119 po~okraji bloku touto hranou (tím vytvoří novou stěnu) a také může
 120 sloučit několik bloků do~jednoho, jak je vidět z~obrázků.
 121
 122 \separatefix{
 123 \figure{planar1.epdf}{Před nakreslením zpětných hran \dots}{}
 124 \figure{planar2.epdf}{\dots\ po něm (čtverečky jsou externí vrcholy)}{}
 125 }
 126
 127 Bude se nám hodit, že čas potřebný na~tuto operaci je přímo úměrný počtu
 128 hran, které ubyly z~vnější stěny, což je amortizovaně konstanta.
 129
 130 Může se nám ale také stát, že zpětná hrana zakryje nějaký externí vrchol.
 131 Tehdy musíme některé bloky překlopit tak, aby externí vrcholy
 132 zůstaly venku. Potřebujeme tedy datové struktury, pomocí nichž bude možné
 133 překlápět efektivně a co víc, také rychle poznávat, kdy je překlápění potřebné.
 134
 135 \h{Externí vrcholy}
 136
 137 Jestliže z~nějakého vrcholu~$v$ bloku~$B$ vede dosud nenakreslená hrana, musí
 138 být tento vrchol na~vnější stěně, takže musí také zůstat na~vnější stěně
 139 i~vrchol, přes který je~$B$ připojen ke~zbytku grafu. Proto externost
 140 nadefinujeme tak, aby pokrývala i tyto případy:
 141
 142 \s{Definice:} Vrchol~$w$ je {\I externí,} pokud buďto z~$w$ vede zpětná
 143 hrana do~ještě nenakresleného vrcholu, nebo je pod~$w$ připojen externí
 144 blok, čili blok obsahující alespoň jeden externí vrchol. Ostatním vrcholům
 145 budeme říkat {\I interní.}
 146
 147 Jinými slovy platí, že vrchol $w$ je externí při zpracování vrcholu~$v$, pakliže $\<Ancestor>(w) < \<Enter>(v)$,
 148 nebo pokud pro některého ze~synů $x$ ležícího v~jiném bloku je $\<LowPoint>(x) < \<Enter>(v)$.
 149 Druhá podmínka funguje díky tomu, že kořen bloku má v~tomto bloku právě jednoho syna
 150 (jinak by existovala příčná hrana, což víme, že není pravda), takže minimum z~\<Ancestor>ů
 151 všech vrcholů ležících uvnitř bloku a v~podřízených blocích je přesně \<LowPoint> tohoto syna.
 152 Ve~statickém grafu by se všechny testy redukovaly na~$\<LowPoint>(w)$, nám se ovšem bloková
 153 struktura průběžně mění, takže musíme uvažovat bloky v~současném okamžiku. Proto si zavedeme:
 154
 155 \s{Definice:} $\<BlockList>(w)$ je seznam všech bloků připojených v~daném okamžiku
 156 pod vrcholem~$w$, reprezentovaných jejich kořeny (klony vrcholu~$w$) a jedinými syny kořenů.
 157 Tento seznam udržujeme setříděný vzestupně podle $\<LowPoint>$ů synů.
 158
 159 \s{Lemma:} Vrchol~$w$ je externí při zpracování vrcholu~$v$, pokud je buďto $\<Ancestor>(w) < \<Enter>(v)$,
 160 nebo první prvek seznamu $\<BlockList>(w)$ má $\<LowPoint> < \<Enter>(v)$. Navíc
 161 seznamy \<BlockList> lze udržovat v~amortizovaně konstantním čase.
 162
 163 \proof První část plyne přímo z~definic. Všechny seznamy na~začátku běhu algoritmu
 164 sestrojíme v~lineárním čase přihrádkovým tříděním a kdykoliv sloučíme blok
 165 s~nadřazeným blokem, odstraníme ho ze~seznamu v~příslušné artikulaci.
 166 \qed
 167
 168 \h{Reprezentace bloků a překlápění}
 169
 170 Pro každý blok si potřebujeme pamatovat vrcholy, které leží na~hranici
 171 (některé z~nich jsou externí, ale to už umíme poznat) a bloky,
 172 které jsou pod nimi připojené. Dále ještě vnitřní strukturu bloku včetně
 173 uvnitř připojených dalších bloků, ale jelikož žádné vnitřní vrcholy nejsou
 174 externí, vnitřek už neovlivní další výpočet a potřebujeme jej pouze
 175 pro vypsání výstupu.
 176
 177 Pro naše účely bude stačit zapamatovat si u~každého bloku, jestli je
 178 oproti nadřazenému bloku překlopen. Tuto informaci zapíšeme do~kořene
 179 bloku. Každý vrchol na~hranici bloku pak bude obsahovat dva~ukazatele
 180 na~sousední vrcholy. Neumíme sice lokálně poznat, který ukazatel odpovídá
 181 kterému směru, ale když se nějakým směrem vydáme, dokážeme ho dodržet
 182 -- stačí si vždy vybrat ten ukazatel, který nás nezavede do~právě
 183 opuštěného vrcholu.
 184
 185 Každý vrchol si také bude pamatovat seznam svých sousedů,
 186 podle orientace bloku buďto v~hodinkovém nebo opačném pořadí.
 187 Chceme-li přidat hranu, potřebujeme tedy znát absolutní orientaci,
 188 ale to půjde snadno, jelikož hrany přidáváme jen k~vrcholům na~hranici,
 189 poté co k~nim po~hranici dojdeme z~kořene.
 190
 191 K~překlopení bloku včetně všech podřízených bloků nám stačí invertovat
 192 bit v~kořeni, pokud chceme překlopit jen tento blok, invertujeme bity
 193 i v~kořenech všech podřízených bloků, jež najdeme obcházením hranice.
 194
 195 Na~konci algoritmu spustíme dodatečný průchod, který všechny překlápěcí
 196 bity přenese ve~směru od~kořene k~potomkům a určí tak absolutní orientaci
 197 všech seznamů sousedů i hranic.
 198
 199 \h{Živý podgraf}
 200
 201 Když nakreslíme nový vrchol~$v$ a z~něj vedoucí stromové hrany, musíme obejít
 202 každý podstrom, ve~vhodném pořadí nakreslit zpětné hrany do~$v$ a podle
 203 potřeby překlopit bloky. V~podstromu ovšem může být mnoho bloků, které
 204 žádnou pozornost nevyžadují a běh algoritmu by zbytečně brzdily.
 205 Proto si před samotným kreslením označíme {\I živou} část grafu -- to je
 206 část, kterou potřebujeme během kreslení navštívit; zbytku grafu se budeme
 207 snažit vyhýbat, aby nás nezdržoval.
 208
 209 \s{Definice:}
 210 Vrchol~$w$ je {\I živý,} pokud z~něj buďto vede zpětná hrana do~právě
 211 zpracovávaného vrcholu~$v$, nebo pokud pod ním je připojen živý blok,
 212 tj. blok obsahující živý vrchol.
 213
 214 Živé vrcholy přitom mohou být i~externí (pokud z~nich vedou zpětné hrany
 215 jak do vrcholu~$v$, tak do ještě nenakreslených vrcholů).
 216 Pokud nějaký vrchol není ani živý, ani externí, budeme ho nazývat {\I pasivní.}
 217
 218 Před procházením podstromů tedy nejprve probereme všechny zpětné hrany vedoucí do~$v$
 219 a označíme živé vrcholy. Pro každou zpětnou hranu potřebujeme oživit vrchol, z~nějž
 220 hrana vede, dále artikulaci, pod~níž je tento blok připojen, a další artikulace
 221 na~cestě do~$v$. Tedy pokaždé, když vstoupíme do~bloku (nějakým vrcholem na~vnější stěně),
 222 potřebujeme nalézt kořen bloku. To uděláme tak, že začneme obcházet vnější
 223 stěnu oběma směry současně, až dojdeme v~některém směru do~kořene. Navíc si všechny
 224 vrcholy, přes něž jsme prošli, označkujeme a přiřadíme k~nim rovnou ukazatel na~kořen,
 225 tudíž po~žádné části hranice neprojdeme vícekrát.\foot{Značky ani nebude potřeba
 226 mazat, když si u nich poznamenáme, který vrchol byl kořenem v~okamžiku, kdy jsme
 227 značku vytvořili, a značky patřící ke~starým kořenům budeme ignorovat, resp. přepisovat.}
 228
 229 Výstupem této části algoritmu budou značky u~živých vrcholů a u~artikulací
 230 také seznamy podřízených živých bloků. Tyto seznamy budeme udržovat uspořádané
 231 tak, aby externí bloky následovaly po~všech interních. To nám usnadní práci
 232 v~hlavní části algoritmu.
 233
 234 \s{Lemma:} Pro každý kořen trvá značení živých vrcholů čas $\O(k+\ell)$, kde $k$ je počet
 235 kreslených zpětných hran a $\ell$ počet hran, které zmizely z~vnější stěny, čili
 236 amortizovaně konstanta.
 237
 238 \proof
 239 Po~žádné hraně neprojdeme více než jednou. Navíc alespoň polovina z~těch, po~nichž
 240 jsme prošli, zmizí z~vnější stěny, takže hledání kořenů bloků trvá $\O(\ell)$.
 241 Pro každou zpětnou hranu označíme jeden vrchol jako živý a pak pokračujeme hledáním
 242 kořenů, které jsme již započítali.
 243 \qed
 244
 245 \h{Kreslení zpětných hran}
 246
 247 Nyní již máme vše připraveno -- datové struktury, detekci externích vrcholů
 248 a označování živého podgrafu -- a zbývá doplnit, jak algoritmus kreslí zpětné
 249 hrany. Jelikož zpětné hrany vedoucí do~$v$ nemohou způsobit sloučení bloků
 250 ležících pod~$v$ (na~to jsou potřeba zpětné hrany vedoucí někam nad~$v$ a ty
 251 ještě nekreslíme), zpracováváme každý podstrom zvlášť. Vždy přidáme triviální blok
 252 pro stromovou hranu, pod něj připojíme blokovou strukturu zatím nakreslené
 253 části podstromu a vydáme se po~hranici této struktury nejdříve jedním
 254 a pak druhým směrem.
 255
 256 Oba průchody vypadají následovně: Procházíme seznam vrcholů na~hranici a pasivní
 257 vrcholy přeskakujeme. Pokud objevíme živý vrchol, nakreslíme vše, co z~něj vede,
 258 případně se zanoříme do~živých bloků, které jsou připojeny pod tímto vrcholem.
 259 Pokud objevíme externí vrchol (poté, co jsme ho případně ošetřili jako živý),
 260 procházení zastavíme, protože za externí vrchol již nemůžeme po~této straně
 261 hranice nic připojit, aniž by se externí vrchol dostal dovnitř nakreslení.
 262
 263 Přitom se řídíme dvěma jednoduchými pravidly:
 264
 265 \s{Pravidlo \#1:} V~každém živém vrcholu zpracováváme nejdříve zpětné hrany do~$v$,
 266 pak podřízené živé interní bloky a konečně podřízené živé externí bloky.
 267 (K~tomu se nám hodí, že máme seznamy živých podřízených bloků setříděné.)
 268
 269 \s{Pravidlo \#2:} Pokud vstoupíme do~dalšího bloku, vybereme si směr, ve~kterém
 270 budeme pokračovat, následovně: preferujeme směr k~živému internímu
 271 vrcholu, pokud takový neexistuje, pak k~živému externímu vrcholu.
 272 Pokud se tento směr liší od~směru, ve~kterém jsme zatím hranici obcházeli,
 273 blok překlopíme.
 274
 275 Časová složitost této části algoritmu je lineární ve~velikosti živého podgrafu
 276 až na~dvě výjimky. Jednou je konec prohledávání od~posledního živého vrcholu
 277 k~bodu zastavení, druhou pak vybírání strany hranice při vstupu do~bloku.
 278 V~obou můžeme procházet až lineárně mnoho pasivních vrcholů. Pomůžeme si
 279 ovšem snadno: kdykoliv projdeme souvislý úsek hranice tvořený pasivními
 280 vrcholy, přidáme pomocnou hranu, která tento úsek překlene. Můžeme ji dokonce
 281 přidat do~nakreslení a podrozdělit si tak vnější stěnu.
 282
 283 \h{Hotový algoritmus}
 284
 285 \s{Algoritmus (kreslení do roviny):}
 286
 287 \algo
 288 \:Pokud má graf více než $3n-6$ hran, odmítneme ho rovnou jako nerovinný.
 289 \:Prohledáme graf $G$ do~hloubky, spočteme \<Enter,> \<Ancestor> a \<LowPoint> všech vrcholů.
 290 \:Vytvoříme \<BlockList> všech vrcholů přihrádkovým tříděním.
 291 \:Procházíme vrcholy v~pořadí klesajících \<Enter>ů, pro každý vrchol~$v$:
 292 \::Nakreslíme všechny stromové hrany z~$v$ jako triviální bloky \hfil\break (2-cykly).
 293 \::Označíme živý podgraf.
 294 \::Pro každého syna vrcholu~$v$ obcházíme živý podgraf náležící k~tomuto vrcholu
 295    v~obou směrech a kreslíme zpětné hrany do~$v$.
 296 \::Zkontrolujeme, zda všechny zpětné hrany vedoucí do~$v$ byly nakresleny, a pokud ne,
 297    prohlásíme graf za~nerovinný a skončíme.
 298 \:Projdeme hotové nakreslení do~hloubky a zorientujeme seznamy sousedů.
 299 \endalgo
 300
 301 \s{Věta:} Tento algoritmus pro každý graf doběhne v~čase $\O(n)$ a pokud byl graf rovinný,
 302 vydá jeho nakreslení, v~opačném případě ohlásí nerovinnost.
 303
 304 \proof První krok je korektní, jelikož pro všechny rovinné grafy je $m\le 3n-6$; nadále
 305 tedy můžeme předpokládat, že $m=\O(n)$. Lineární časovou složitost kroků 4--6 a~9 jsme již
 306 diskutovali, kroky~7--8 jsou lineární ve~velikosti živého podgrafu, a~tedy také $\O(n)$.
 307 Nakreslení vydané algoritmem je vždy rovinné a všechny stromové hrany jsou vždy
 308 nakresleny, zbývá tedy ukázat, že zpětnou hranu můžeme nenakreslit, jen pokud
 309 graf nebyl rovinný. Tomu věnujeme zbytek kapitoly.
 310 \qed
 311
 312 \h{Důkaz korektnosti}
 313
 314 \s{Lemma:} Pokud existuje zpětná hrana, kterou algoritmus nenakreslil, graf na~vstupu
 315 není rovinný.
 316
 317 \proof Pro spor předpokládejme, že po~zpracování vrcholu~$v$ existuje nějaká
 318 zpětná hrana~$wv$, kterou algoritmus nenakreslil. Tedy přístup z~$v$ k~$w$
 319 je v~obou směrech blokován externími vrcholy. Rozborem případů ukážeme,
 320 že pokud jsme se důsledně řídili pravidly \#1 a \#2, může se to stát pouze
 321 v~nerovinném grafu.
 322
 323 {\I Překážející blok.}
 324 Uvažme posloupnost bloků vedoucí od vrcholu~$v$ k~$w$. V~této posloupnosti se
 325 musí vyskytovat nějaký blok~$B$, který má na obou stranách hranice aspoň jeden
 326 externí vrchol -- jinak bychom totiž bloky popřeklápěli tak, abychom se dostali až do~$w$.
 327 Označme~$x$ externí vrchol na levé straně hranice bloku~$B$, $y$~ten na pravé.
 328 Vrcholy $x$, $y$, $v$ a~$w$ jsou zjevně navzájem různé.
 329
 330 {\I Nadřazené bloky.}
 331 Nejprve ukážeme, že kořenem bloku~$B$ musí být přímo vrchol~$v$. Kdyby totiž
 332 mezi~$v$ a~$B$ ležely nějaké další bloky, našli bychom v~grafu minor~$M$ z~následujícího
 333 obrázku, který je isomorfní s~grafem $K_{3,3}$. Do vrcholu~$u$ jsme zkontrahovali
 334 ještě nenakreslenou část grafu, do~$v$ všechny bloky ležící nad~$B$, do~$x$ a~$y$
 335 případné podřízené externí bloky (díky nimž se $x$ a~$y$ staly externími) a do~$w$
 336 všechny bloky ležící mezi~$B$ a~$w$.
 337
 338 Blok~$B$ je tedy nejvyšší a přímo obsahuje vrchol~$v$. Této situaci odpovídá
 339 minor~$N$, který je ovšem rovinný, takže na prokázání nerovinnosti grafu budeme
 340 muset zkoumat vnitřek bloku.
 341
 342 {\I Podřízené bloky.}
 343 Předtím ale rozebereme případ, kdy vrchol~$w$ neleží přímo v~bloku~$B$, nýbrž
 344 v~nějakém podřízeném bloku, který je připojen pod nějakou artikulací $w'\in B$.
 345 Tento podřízený blok přitom nemůže být externí: kdyby byl, najdeme v~grafu
 346 minor~$P$ obsahující $K_{3,3}$. Tedy není externí, takže vstoupíme-li během obcházení
 347 do~$w'$, pravidlo~\#2 zaručí, že dojdeme do~$w$ a díky pravidlu~\#1 vzápětí
 348 nakreslíme hranu~$wv$. Tu jsme nenakreslili, takže jsme nedošli ani do~$w'$.
 349 Můžeme proto bez újmy na obecnosti předpokládat, že hrana $wv$ vede přímo
 350 z~bloku~$B$.
 351
 352 \bigskip
 353 \centerline{\putepdf{}{pl-minor1.pdf}\qquad\putepdf{}{pl-minor2.pdf}}
 354 \bigskip
 355 \centerline{\putepdf{}{pl-minor3.pdf}\qquad\putepdf{}{pl-minor4.pdf}}
 356 \bigskip
 357 \centerline{\putepdf{}{pl-minor5.pdf}\qquad\putepdf{}{pl-minor6.pdf}}
 358 \bigskip
 359
 360 {\I Existence plotu.}
 361 Stačí se tedy omezit na situaci s~jediným blokem~$B$, v~němž leží vrcholy~$v$, $w$,
 362 $x$ i~$y$. Dokážeme nyní, že uvnitř bloku existuje {\I plot} -- cesta mezi~$x$
 363 a~$y$, jejíž zbývající vrcholy neleží na hranici bloku.
 364
 365 Předpokládejme pro spor, že plot neexistuje. Před nakreslením zpětných hran
 366 vedoucích do~$v$ ještě blok~$B$ neexistoval a jeho hrany patřily do několika
 367 menších bloků. Speciálně víme, že $w$~byla artikulace oddělující $x$ od~$y$,
 368 takže každá cesta mezi~$x$ a~$y$ musela procházet přes~$w$. Proto v~pořadí podle DFS
 369 musí ležet~$w$ před aspoň jedním z~vrcholů $x$ a~$y$. Buď~$x$ nebo~$y$ tedy předtím musel
 370 ležet v~nějakém podřízeném bloku pod~$w$. A~z~nějakého takového bloku také musela
 371 vést zpětná hrana (tehdy ještě externí) do~$v$, která později uzavřela blok~$B$.
 372 K~této hraně jsme se museli během obcházení dostat, a~to je možné pouze přes~$w$.
 373 Vrchol~$w$ tedy musel být navštíven a hrana $wv$ nakreslena, což je spor.
 374
 375 {\I Nejvyšší plot.}
 376 Plot tedy existuje. Zvolíme mezi všemi ploty ten nejvyšší, čili nejbližší k~$v$
 377 (rozmyslete si, že to je v~rovinném nakreslení dobře definované). Označme $p_x$~vrchol,
 378 v~němž se plot napojuje na levou cestu z~$v$ do~$w$, a~obdobně~$p_y$ na pravé cestě. Rozmyslíme si,
 379 jak může situace vypadat.
 380
 381 {\bf A.} Předně žádný z~vrcholů $p_x$ a~$p_y$ nemůže být blíž k~$v$ než $x$ a~$y$. Pokud by
 382 bez újmy na obecnosti $p_x$~ležel mezi $v$ a~$x$, našli bychom v~grafu minor~$N_A$ obsahující $K_{3,3}$:
 383 cestu mezi $y$ a~$p_y$ jsme zkontrahovali do~$y$, celý plot jsme zkontrahovali do hrany~$p_xy$,
 384 ostatní vrcholy jsou utvořeny stejně jako v~předchozích minorech.
 385
 386 {\bf B.} Dále ukážeme, že plot může být připojen k~$v$ pouze přes $p_x$ a~$p_y$. V~opačném
 387 případě by se v~grafu vyskytoval minor~$N_B$ obsahující $K_{3,3}$: do~$x$ jsme zkontrahovali
 388 cestu mezi $x$ a~$p_x$, podobně do~$y$ cestu mezi $y$ a~$p_y$.
 389
 390 {\bf C.} Nakonec se přesvědčíme, že na dolní cestě z~$x$ do~$y$ přes~$w$ nemůže ležet
 391 žádný externí vrchol. To by totiž způsobovalo minor~$N_C$ isomorfní s~$K_5$:
 392 do~$w$ jsme zkontrahovali cestu mezi externím vrcholem a~$w$ a také všechny
 393 případné podřízené bloky až k~externí hraně.
 394
 395 {\I Vnitřek bloku~$B$.}
 396 Nyní uvažujme, jak graf vypadal před nakreslením vrcholu~$v$. I~tehdy musel plot
 397 společně s~dolní cestou ležet v~jednom bloku. Tento blok musel být z~jedné strany připojený
 398 nenakreslenými hranami k~$v$ přes~$p_x$, z~druhé přes~$p_y$ (a~díky vlastnosti~{\bf B} nikudy jinudy).
 399 Říkejme tomuto bloku~$B'$ a~označme $r_1\in\{p_x,p_y\}$ jeho kořen a $r_2$ druhý
 400 z~vrcholů $p_x,p_y$.
 401
 402 Jelikož jsme nakonec nakreslili zpětnou hranu uzavírající blok~$B$, museli jsme
 403 někdy dojít do~$r_1$. V~tomto okamžiku:
 404
 405 \itemize\ibull
 406 \:Díky {\bf A:} $r_2$~je předkem $x$ nebo~$y$ (případně je takovému vrcholu roven),
 407 takže je nyní externí.
 408 \:Díky {\bf B:} půjdeme-li z~$r_1$ po plotu, nejbližší \uv{zajímavý} vrchol bude~$r_2$.
 409 \:Díky {\bf C:} žádný vrchol na dolní cestě není externí.
 410 \endlist
 411
 412 Při vstupu do~$r_1$ tedy plot vede k~externími vrcholu, zatímco dolní cesta
 413 k~internímu. Podle pravidla \#2 si algoritmus musí vybrat dolní cestu, kde ho
 414 nic nezastaví, takže dojde až do~$w$ a~nakreslí zpětnou hranu $wv$. To je opět spor.
 415 \qed
 416
 417 \s{Poznámka:} Podle tohoto důkazu bychom také mohli v~lineárním čase v~každém nerovinném
 418 grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jelikož když je $m>3n-6$,
 419 můžeme se omezit na~libovolných $3n-5$ hran, které určitě tvoří nerovinný podgraf.
 420
 421 \references
 422 \bye