\chapter{Kreslenie z\'akladn\'ych grafov a v\v seobecn\'e met\'ody}
%!
%!
\hyphenation{na-kre-sle-n\'e-ho pla-n\'ar-nych kom-bi-na-to-ric-k\'y n\'a-kres}
%!
%!
%!
V tejto kapitole uvedieme met\'ody kreslenia z\'akladn\'ych
grafov ako s\'u stromy (zakorenen\'y aj nezakorenen\'y),
kompletn\'e grafy, \v dalej met\'ody kreslenia plan\'arnych grafov, ktor\'e
s\'u ve\v lmi d\^ole\v zit\'e v graph drawingu. Potom uk\'a\v zeme
najpou\v z\'ivanej\v sie met\'ody kreslenia v\v
seobecn\'ych grafov a uvedieme v\'yhody a nev\'yhody t\'ychto
met\'od.
%!
%!
\section{Kreslenie stromov}
%!
%! presiel\dobre\literatura\literatura.pdf
%! ako kreslit stromy + obrazok nakresleneho zakoreneneho ztromu
%!
\subsection{Zakorenen\'y strom}
Zakorenen\'y strom obsahuje v\'yzna\v cn\'y vrchol, ktor\'y sa
naz\'yva kore\v n. Stromov\'a \v strukt\'ura je v informatike \v
casto pou\v z\'ivan\'a, napr. pri ukladan\'i inform\'aci\'i,
preh\v lad\'avan\'i a podobne. Na kreslenie stromov sa pou\v
z\'iva straight-line drawing alebo ortogonal polyline drawing.
Ke\v d\v ze strom neobsahuje cyklus, tak sa d\'a v\v zdy
nakresli\v t plan\'arne. Zvy\v cajne sa db\'a na nasleduj\'uce
estetick\'e krit\'eri\'a :
%!
%!
\begin{enumerate}
\item Vrcholy s\'u umiestnen\'e pozd\'l\v z horizont\'alnych \v
ciar prisl\'uchaj\'ucich ich \'urovni (vzdialenos\v t od korena)
%!
\item Je minim\'alna vzdialenos\v t medzi dvoma nasleduj\'ucimi
vrcholmi na rovnakej \'urovni
%!
\item \v S\'irka n\'akresu je \v co najmen\v sia
%!
\item Otcovsk\'y vrchol m\'a synov nakreslen\'ych pri sebe
%!
\item Naviac, ak je strom usporiadan\'y a bin\'arny (ako napr.
bin\'arny vyh\v lad\'avac\'i strom), tak \v lav\'y a prav\'y syn vrcholu
$v$ s\'u umiestnen\'e v\v lavo respekt\'ive vpravo od $v$
\end{enumerate}
Nakreslenie stromu pod\v la t\'ychto krit\'eri\'i je na obr\'azku
\ref{fig:strom}.
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.6\textwidth]{obrazky/strom.eps}
\caption{Nakreslenie zakorenen\'eho stromu}
\label{fig:strom}
\end{center}
\end{figure}
%!
%!
%!
\subsection{Vo\v ln\'y strom}
Vo\v ln\'y strom nereprezentuje \v ziadnu hierarchiu a nem\'a
kore\v n. Algoritmy pre kreslenie zakorenen\'ych stromov mo\v zu
by\v t upraven\'e pre nakreslenie vo\v ln\'eho stromu napr\'iklad
tak, \v ze za kore\v n zvol\'ime nejak\'y vhodn\'y vrchol (napr.
vrchol s najmen\v sou vzdialenos\v tou od ostatn\'ych, alebo
centr\'alny vrchol). \v Dal\v s\'i pr\'istup je ten, \v ze m\^o\v
zeme vrcholy v ka\v zdej \'urovni nakresli\v t na s\'ustredn\'e
kru\v znice vzh\v ladom na nejak\'y zvolen\'y stred grafu (Obr\'azok
\ref{fig:korstrom}).
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.42\textwidth]{obrazky/korstrom.eps}
\caption{Nakreslenie nezakorenen\'eho stromu pomocou s\'ustredn\'ych kru\v zn\'ic}
\label{fig:korstrom}
\end{center}
\end{figure}
%!
%!
%!
\section{Kreslenie plan\'arnych grafov}
%!
%! teraz\Weiskircher01.pdf
%! definicia planarnej reprezentacie, planarneho grafu, planarnej embedding, subdivicie,
%! veta kedy je graf planarny, kratky popis 2ch linearnych algoritmov na testovanie planarity,
%! splanarnenie grafu pomocou vertex splitting, vkladanim vrcholov a mazanim hran, definicia maximalneho
%! planarneho podgrafu
%!
%!
Defin\'icie t\'ykaj\'uce sa plan\'arnych grafov a algoritmy na ich kreslenie n\'ajdeme v~\cite{plan}.
Ak m\'ame neohrani\v cen\'u plochu a chceme do nej nakresli\v t
plan\' arny graf, tak po\v cet v\v setk\'ych r\^oznych
nakreslen\'i nie je kone\v cn\'y. Tieto nakreslenia sa ale daj\'u
rozdeli\v t do tried ekvivalencie, pod\v la toho ak\'e cykly vrcholov s\'u
v plan\'arnom nakreslen\'i. T\'ychto tried ekvivalenie je preto
kone\v cn\'y po\v cet, ale m\^o\v ze ich by\v t a\v z
exponenci\'alne ve\v la. Jedna tak\'ato trieda ekvivalencie sa
naz\'yva plan\'arne ulo\v zenie.
%!
%!
\newtheorem{planemb}{Defin\'icia}[section]
\begin{planemb}
Dve reprezent\'acie $D_1$ a $D_2$ plan\'arneho grafu $G$, patria
do tej istej triedy ekvivalencie plan\'arneho ulo\v zenia
(planar embedding) pr\'ave vtedy, ke\v d s\'u splnen\'e
nasleduj\'uce podmienky~:
\begin{itemize}
\item Jednoduch\'e cykly vrcholov v $G$, ktor\'e via\v zu oblasti v $D_1$ s\'u rovnak\'e cykly vrcholov, ak\'e
via\v zu oblasti v $D_2$.
\item Vonkaj\v sia oblas\v t v $D_1$ je viazan\'a rovnak\'ym cyklom vrcholov z $G$ ako v $D_2$.
\end{itemize}
\end{planemb}
%!
%!
Planarita grafu je ve\v lmi d\^ole\v zit\'a vlastnos\v t. Na
zistenie \v ci je graf plan\'arny potrebujeme zadefinova\v t pojem
subdiv\'izia grafu. Je to graf, ktor\'y vznikne tak, \v ze
niektor\'e hrany p\^ovodn\'eho grafu s\'u nahraden\'e cestami, na
ktor\'ych je ka\v zd\'y vrchol stup\v na dva.
%!
%!
\newtheorem{subdiv}[planemb]{Defin\'icia}
\begin{subdiv}
Subdiv\'izia grafu $G=(V,E)$ je graf $G'=(V',E')$, ktor\'y
vznikne z $G$ postupnos\v tou oper\'aci\'i $split$, ktor\'a
pozost\'ava z vlo\v zenia nov\'eho vrchola $u$ a nahraden\'im
hrany $e=(v_1,v_2)$ dvoma hranami $e_1=(v_1,u)$ a $e_2=(u,v_2)$.
\end{subdiv}
%!
%!
Teraz u\v z m\^o\v zeme plan\'arne grafy presne ur\v ci\v t pomocou nasleduj\'ucej vety.
%!
%!
\newtheorem{kuratowski}[planemb]{Veta}
\begin{kuratowski}[Kuratowski]
Graf $G$ je plan\'arny pr\'ave vtedy, ke\v d neobsahuje
subdiv\'iziu $K_5$ ani $K_{3,3}$. \label{veta:kurat}
\end{kuratowski}
%!
\begin{proof}
P\^ovodn\'y Kuratowsk\'eho d\^okaz n\'ajdeme v \cite{kuratow}, kr\'atky kombinatorick\'y d\^okaz je v \cite{yury}.
\end{proof}
\newline
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.6\textwidth]{obrazky/k5_k33.eps}
\caption{Dva z\'akladn\'e neplan\'arne grafy : $K_{3,3}$ a $K_5$}
\label{fig:k5_k33}
\end{center}
\end{figure}
%!
%!
\newline
Testovanie planarity je ve\v lmi d\^ole\v zit\'e pri kreslen\'i
grafov a vyu\v z\'iva sa tak pri kreslen\'i plan\'arnych grafov
ako aj v niektor\'ych met\'odach kreslenia v\v seobecn\'ych
grafov.
Prv\'y algoritmus na testovanie \v ci je graf plan\'arny
vymysleli Auslander a Parter (1961) a Goldstein (1963). Hopcroft a
Tarjan zlep\v sili tento v\'ysledok na algoritmus, ktor\'y be\v
z\'i v line\'arnom \v case (1974). \v Dal\v s\'i line\'arny
algoritmus na testovanie planarity vymysleli Lempel, Even a
Cederbaum (1967) a Booth a Lueker (1976).
%!
%!
\newtheorem{testplan}[planemb]{Veta}
\begin{testplan}
Testovanie planarity a zostrojenie plan\'arnej reprezent\'acie sa
d\'a spravi\v t v \v case $O(n)$. \label{veta:testplan}
\end{testplan}
%!
\begin{proof}
Algoritmus Hopcrofta a Tarjana z roku 1974 n\'ajdeme v \cite{hop_tar}.
%!This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an %!iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first %!search and has O(V) time and space bounds, where V is the number of vertices in G. An ALGOL implementation of the algorithm succesfully tested graphs %!with as many as 900 vertices in less than 12 seconds.
\end{proof}
%!
%!
\newline
\newline
%!
%!
Pri kreslen\'i grafov je \v casto dobr\'e vedie\v t, ak\'e ve\v
lk\'e bude nakreslenie grafu vzh\v ladom na po\v cet jeho
vrcholov. Je d\^ole\v zit\'e aby sme vedeli, ak\'u ve\v lk\'u
plochu m\'ame pre dan\'y graf rezervova\v t, alebo pri ohrani\v
cenej ploche zisti\v t, \v ci sa do nej d\'a dan\'y graf v\^obec
nakresli\v t.
%!
%!
\newtheorem{veta1}[planemb]{Veta}
\begin{veta1}
Ka\v zd\'y $n$-vrcholov\'y plan\'arny graf m\'a straight-line plan\'arny n\'akres
(sie\v t, mrie\v zka), ktor\'y je ohrani\v cen\'y obd\v l\v znikom s rozmermi $O(n) * O(n)$.
\end{veta1}
%!
\begin{proof}
Kon\v struk\v cn\'y d\^okaz n\'ajdeme v~\cite{liu}, je tam
algoritmus pracuj\'uci v line\'arnom \v case a kresliaci do obd\'l\v znika velkosti (2n-4)x(n-2).
\end{proof}
%!
%!
\newline
\newline
%!
%!
Algoritmy na kreslenie plan\'arnych grafov maj\'u zvy\v cajne tak\'uto \v strukt\'uru~:
%!
%! presiel\dobre\literatura\literatura.pdf        -> mam v literature
%! tento krokovy popis + obrazok K3,3 ako sa nakresli takto
%!
%!
\begin{enumerate}
\item Test planarity -- existuj\'u line\'arne algoritmy, ale v\v
setky s\'u zlo\v zit\'e na implement\'aciu a pochopenie
%!
\item Zostrojenie plan\'arnej reprezent\'acie
%!
\item Pou\v zitie plan\'arnej reprezent\'acie na nakreslenie grafu
pod\v la ur\v cit\'ych grafick\'ych \v standardov
\end{enumerate}
Existuj\'u algoritmy, ktor\'e spravia kroky 1 a 2 v line\'arnom \v
case (pozri Veta~\ref{veta:testplan}).
%!
%!
%!
\section{Kreslenie kompletn\'ych grafov}
%!
%!
Kompletn\'y graf sa oby\v cajne kresl\'i tak, \v ze v\v setky
vrcholy le\v zia na kru\v znici a s\'u rozvrhnut\'e rovnomerne
(Obr\'azok \ref{fig:k7}). Tak\'yto n\'akres je maxim\'alne
symetrick\'y. Pri kreslen\'i kompletn\'eho grafu je ve\v lmi \v
ta\v zk\'e predch\'adza\v t kr\'i\v zeniu hr\'an, ke\v d\v ze u\v
z $K_5$ nie je plan\'arny (Veta \ref{veta:kurat}) a s ka\v zd\'ym
\v dal\v s\'im vrcholom prib\'uda viac a viac hr\'an.
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.4\textwidth]{obrazky/k7.eps}
\caption{Nakreslenie $K_7$ na kru\v znici}
\label{fig:k7}
\end{center}
\end{figure}
%!
%!
\section{V\v seobecn\'e met\'ody a ich porovnanie}
%!
%! /presiel/dobre/zaklad/gd_tutorial.pdf        -> mam v literature
%! tie to 3 metody + vyhody aj nevyhody
%!
%! /presie/dobre/zaklad/
%!
Na kreslenie v\v seobecn\'ych grafov sa pou\v z\'ivaj\'u r\^ozne
met\'ody. Ka\v zd\'a met\'oda je vhodn\'a na kreslenie in\'ych
grafov a m\'a in\'e vlastnosti. Tak isto je pri v\'ybere met\'ody
d\^ole\v zit\'e, ak\'e krit\'eri\'a m\'a sp\'lna\v t v\'ysledn\'y graf,
a ak\'y typ kreslenia je zvolen\'y. Okrem met\'od pop\'isan\'ych
ni\v z\v sie existuje aj ve\v la \v dal\v s\'ich, napr. met\'oda
zalo\v zen\'a na genetick\'ych algoritmoch\footnote{Tak\'yto algoritmus a jeho porovnanie so spring algoritmom n\'ajdeme v~\cite{genetic}.}. Najpou\v z\'ivanej\v
sie met\'ody s\'u :
%!
\begin{enumerate}
\item Plan\'arne met\'ody\footnote{R\^oznymi met\'odami splan\'ar\v novania grafov sa zaober\'a~\cite{planarizing}.} --- ak graf nie je plan\'arny, tak ho
splan\'arnime (napr. pridan\'im umel\'ych vrcholov, odobrat\'im
hr\'an, rozdelen\'im vrcholov) a pou\v zijeme nejak\'y algoritmus
na kreslenie plan\'arnych grafov, potom sp\"atne vr\'atime graf do
p\^ovodn\'eho stavu % (Obr\'azok \ref{fig:planar})
%!
\item Orientovan\'e met\'ody --- namiesto ka\v zdej hrany sprav\'ime dve orientovan\'e hrany a
pou\v zijeme algoritmus na kreslenie orientovan\'ych grafov
%!
\item Force-direct met\'ody ---  zadefinujeme nejak\'y syst\'em s\'il
na hran\'ach a vrcholoch a n\'ajdeme stav grafu, v ktorom m\'a graf
najmen\v siu energetick\'u hodnotu s\'il (rie\v senie
diferenci\'alnych rovn\'ic alebo simulovanie v\'yvoja syst\'emu),
tieto met\'ody sa vyu\v z\'ivaj\'u v\"a\v c\v sinou na
zobrazovanie stromov\'ych siet\'i, ako napr.~po\v c\'ita\v cov\'e
a soci\'alne siete
\end{enumerate}
%!
%!
%%
%%%%TENTO OBRAZOK NESTIHAM PREKRESLIT !!!
%\begin{figure}[h]
%\begin{center}
%\includegraphics[width=0.6\textwidth]{obrazky/planar.eps}
%\caption{Ortogon\'alne nakreslenie $K_{3,3} $ planariza\v cnou
%met\'odou pridan\'im pr\'azdneho vrcholu : (a) dan\'y graf (b)
%planariz\'acia (c) ortogonaliz\'acia (d) kompakcia}
%\label{fig:planar}
%\end{center}
%\end{figure}
%!
%!
%!
%! \citeseer1_200\behzadi99improved.ps         -> mam v literature
%! strucny popis spring metody str.6, potom ako sa definuju sily v spring algoritme
%! strana 21 -> niektore programi na kreslenie grafov
%!
%! \citeseer1_200\branke96using.ps           -> mam v literature 
%! straightline kreslenie grafu genetickym algoritmom a jeho porovnanie so spring alg.
%!
%! \citeseer1_200\liebers01planarizing.ps       -> mam v literature
%! splanarnenie pomocou mazania vrcholov (strucne), mazanim hran (celkom obsiazne), rozdelovanim
%! vrcholov
%! str.41  hladanie nejmensieho krizoveho cisla (kolko najmenej crossingov)
%!
%! \citeseer1_200\maximum-planar-subgraphs-and.ps       -> mam v literature
%! heuristika na najdenie maximalneho planarneho podgrafu
%!
%! /citeseer1_200/calamoneri99experimental
%! porovnanie metod kreslenia kubickych grafov  -> NEPOTREBNE
%!
%! /citeseer1_200/gansner93technique
%! kreslenie orientovanych grafov, 4 fazovy algoritmus  -> NEPOTREBNE
%!
%!%!  TU ZACINA POROVNANIE METOD  \section{Porovnanie met\'od}
%!
%! /presiel/dobre/zaklad/gd_tutorial.pdf     -> mam uz v literature
%! popis vyhod/nevyhod tychto 2ch metod
%!
%! /presie/dobre/pruzinovy.ps   -> nedal som do literatury
%! posis upraveneho algoritmu zalozeneho na pruzinovom systeme, na lokalnych minimach
%!
Plan\'arna met\'oda m\'a mno\v zstvo v\'yhod, je r\'ychla,
aplikovateln\'a na straight-line, polyline, ortogonal drawing, je
podporovan\'a teoretick\'ymi v\'ysledkami z planar drawingu. Jej
nev\'yhodou je, \v ze je \v ta\v zko implementovateln\'a, a \v
ta\v zko roz\v s\'iriteln\'a na 3D. Oproti tomu je force-direct
met\'oda \v lahko implementovateln\'a, heuristick\'e zlep\v senia
sa \v lahko prid\'avaj\'u, m\^o\v ze by\v t roz\v s\'iriteln\'a na
3D, pracuje dobre pre mal\'e grafy, ale je pomal\'a, existuje
m\'alo teoretick\'ych v\'ysledkov, \v ta\v zko ju roz\v s\'iri\v t
na orthogonal a polyline drawing. Force-direct met\'odou
nakreslen\'e grafy s\'u v\"a\v c\v sinou symetrick\'e, grafy
nakreslen\'e plan\'arnou met\'odou zasa m\'avaj\'u menej kr\'i\v
zen\'i hr\'an\footnote{Porovnanie t\'ychto pr\'istupov kreslenia grafov n\'ajdeme v~\cite{tam4}.}.
%!
\newline
\newline
%!
Jedna z mo\v znost\'i ako splan\'arni\v t dan\'y graf, je odobra\v
t \v co najmen\v s\'i po\v cet hr\'an tak, aby v\'ysledn\'y graf
bol plan\'arny. Potom sa prid\'a hrana tak, aby vzniklo \v co
najmenej kr\'i\v zen\'i. Tam kde vznikn\'u kr\'i\v zenia, sa vlo\v
zia umel\'e vrcholy a znovu sa m\^o\v ze prida\v t \v dal\v sia
hrana, ke\v d\v ze takto vzniknut\'y graf je znovu plan\'arny.
Tak\'yto postup ale nemus\'i vies\v t k nakresleniu, ktor\'e m\'a
minim\'alny po\v cet kr\'i\v zen\'i. D\^ole\v zit\'y krok je
pridanie hrany do planan\'arneho grafu tak, aby vzniklo \v co najmenej
kr\'i\v zen\'i, d\'a sa to spravi\v t v line\'arnom \v case~:
%!
%!
%!
%! presiel\dobre\insert.pdf    -> mam v literature
%! ako vlozit do planarnej konbinacie grafu hranu tak, aby sposobila co najmenej crossings
%! linearny, pomocou SPQR trees, najdenie najkratsej cesty v dualnom grafe
%!
%!
\newtheorem{insert1}{Veta}[section]
\begin{insert1}
%! Mam dany graf G , v1,v2 patria G, najde planarne ulozenie G tak, aby pocet krizeni po
%! vlozeni hrany v1v2 bol minimalny cez vsetky planarne ulozenia grafu G.
Vlo\v zenie hrany (oba koncov\'e vrcholy patria do grafu) do
dan\'eho plan\'arneho grafu tak, aby vzniklo \v co najmenej
kr\'i\v zen\'i sa d\'a v line\'arnom \v case.
\end{insert1}
%!
\begin{proof}
Konceptu\'alne jednoduch\'y line\'arny algoritmus zalo\v zen\'y na
SPQR-stromoch m\^o\v zeme n\'ajs\v t v~\cite{mutzel2}.
\end{proof}
%!
%!
