\chapter{Z\'akladn\'e defin\'icie a algoritmy}
%!
%!
\hyphenation{na-z\'y-va-me ro-vin-n\'u vy-ch\'a-dza-j\'u-ci-mi pla-n\'ar-nym Kra-mer}
%!
%!
%!
%!
V tejto kapitole si uvedieme z\'akladn\'e defin\'icie, \v co je to
graf, podgraf, kompletn\'y graf, strom, komplement grafu,
plan\'arna reprezent\'acia grafu, plan\'arny graf\footnote{V\v setky ostatn\'e defin\'icie t\'ykaj\'uce sa grafov sa 
nach\'adaj\'u v~\cite{dies} alebo v~\cite{planet}.}. \v Dalej sa
budeme venova\v t z\'akladn\'ym pravidl\'am a krit\'eri\'am, na
ktor\'e sa db\'a pri kreslen\'i grafov. Potom si uvedieme
najd\^ole\v zitej\v sie algoritmy kreslenia grafov, NP-\v ta\v
zk\'e a NP-\'upln\'e probl\'emy s\'uvisiace s kreslen\'im grafov ako aj niektor\'e otvoren\'e
probl\'emy z graph drawingu.
%!
%!
\section{Defin\'icie}
%!
%!
Graf sa sklad\'a z vrcholov a hr\'an, pri\v com ka\v zd\'a hrana
sp\'aja dva vrcholy.
%!
\newtheorem{graf}{Defin\'icia}[section]
\begin{graf}
Graf je dvojica $G = (V,E)$ disjunktn\'ych mno\v z\'in, kde
$E\subseteq V^2$. Prvky $V$ s\'u vrcholy grafu $G$ ($V(G)$), prvky
$E$ s\'u jeho hrany ($E(G)$).
\end{graf}
%!
%!
\newtheorem{rad}[graf]{Defin\'icia}
\begin{graf}
Po\v cet vrcholov grafu $G$ naz\'yvame r\'ad grafu $G$ a
ozna\v cujeme $|G|$. Po\v cet jeho hr\'an ozna\v cujeme $||G||$.
\end{graf}
%!
%!
\newtheorem{incid}[graf]{Defin\'icia}
\begin{incid}
Vrchol $v$ je incidentn\'y s hranou $e$, ak je jedn\'ym z
koncov\'ych vrcholov (koncov) hrany $e$. Hovor\'ime, \v ze
hrana $e$ sp\'aja vrcholy, ktor\'e s\'u s \v nou
incidentn\'e. Fakt, \v ze hrana $e$ sp\'aja vrcholy $v_1$ a $v_2$,
ozna\v cujeme $e=(v_1,v_2)$ a hovor\'ime, \v ze vrcholy $v_1$ a
$v_2$ s\'u susedn\'e.
\end{incid}
%!
%!
Podgraf je nejakou podmo\v zinou grafu, obsahuje niektor\'e vrcholy p\^ovodn\'eho grafu a niektor\'e hrany ved\'uce
medzi nimi.
%!
\newtheorem{podgraf}[graf]{Defin\'icia}
\begin{podgraf}
Nech $G=(V,E)$. Graf $G'=(V',E')$, kde $V'\subseteq~V$ a
$E'\subseteq~E$, naz\'yvame podgraf grafu $G$.
\end{podgraf}
%!
%!
K najd\^ole\v zitej\v s\'im triedam grafov patria kompletn\'e
grafy a stromy. Kompletn\'y graf m\'a hrany medzi ka\v zd\'ymi
dvoma r\^oznymi vrcholmi grafu. Strom je s\'uvisl\'y graf, ktor\'y neobsahuje \v
ziaden cyklus. Strom m\^ o\v ze by\v t zakorenen\'y alebo
nezakorenen\'y, pod\v la toho \v ci obsahuje v\'yzna\v cn\'y
vrchol.
%!
%!
\newtheorem{uplny}[graf]{Defin\'icia}
\begin{uplny}
Graf $G$ sa naz\'yva kompletn\'y ak $E(G)=\{ (x,y) | x,y\in
V(G), x\neq y\}$, to znamen\'a, \v ze medzi ka\v zd\'ymi dvoma
r\^oznymi vrcholmi existuje hrana. Ozna\v cujeme ho $K^n$, kde $n$
je po\v cet vrcholov grafu $G$.
\end{uplny}
%!
%!
\newtheorem{strom}[graf]{Defin\'icia}
\begin{strom}
Acyklick\'y graf, t.j. tak\'y, ktor\'y neobsahuje \v ziadne
cykly, naz\'yvame les. S\'uvisl\'y les je strom. \v
Casto je jeden konkr\'etny vrchol stromu ur\v cen\'y ako
kore\v n. Strom, kde je kore\v n ur\v cen\'y sa naz\'yva
zakorenen\'y strom. Strom bez kore\v na sa naz\'yva
nezakorenen\'y (vo\v ln\'y) strom.
\end{strom}
%!
%!
Komplement grafu je jeho doplnok vr\'amci mno\v ziny hr\'an, to
znamen\'a, \v ze obsahuje pr\'ave tie hrany, ktor\'e neobsahoval
p\^ovodn\'y graf.
%!
\newtheorem{komp}[graf]{Defin\'icia}
\begin{komp}
Nech $G$ je graf r\'adu $n$. Graf $G'=K^n-G$ naz\'yvame
komplement grafu $G$.
\end{komp}
%!
%!
Z h\v ladiska vizualiz\'acie grafov je d\^ ole\v zit\'a mno\v zina
grafov, ktor\'e sa naz\'yvaj\'u plan\'arne. Maj\'u t\'u vlastnos\v
t, \v ze ich m\^o\v zeme nakresli\v t do roviny tak, aby sa \v
ziadne dve hrany grafu nepret\'inali.
%!
\newtheorem{planrep}[graf]{Defin\'icia}
\begin{planrep}
Plan\'arna reprezent\'acia grafu $G$ je jeho zakreslenie na rovinn\'u plochu tak,
\v ze vrcholy nahrad\'ime bodmi a hrany jednoduch\'ymi krivkami. Hrany grafu sa pri plan\'arnej
reprezent\'acii nesm\'u pret\'ina\v t.
\end{planrep}
%!
%!
\newtheorem{plangraf}[graf]{Defin\'icia}
\begin{plangraf}
Graf, pre ktor\'y existuje plan\'arna reprezent\'acia, sa naz\'yva plan\'arny graf.
\end{plangraf}
%!
%!
%!
\section{Pravidl\'a a krit\'eri\'a}
Pri kreslen\'i grafov sa dodr\v zuj\'u ur\v cit\'e pravidl\'a, aby
v\'ysledn\'e nakreslenie grafu nevypadalo pr\'ili\v s zle a aby bolo
lep\v sie pou\v zite\v ln\'e. Najd\^ole\v zitej\v sie s\'u celo\v
c\'iseln\'e s\'uradnice vrcholov a aby vz\'ajomn\'e vzdialenosti
jednotliv\'ych elementov grafu neboli pr\'ili\v s mal\'e.
Pravidl\'a pri kreslen\'i grafov~:
\begin{itemize}
\item Celo\v c\'iseln\'e s\'uradnice pre vrcholy a ohyby
%!
\item Predp\'isan\'a minim\'alna vzdialenos\v t medzi vrcholmi
%!
\item Predp\'isan\'y minim\'alny uhol medzi dvoma susedn\'ymi
hranami vych\'adzaj\'ucimi z toho ist\'eho vrcholu (Obr\'azok
\ref{fig:pravidla})
%!
\item Predp\'isan\'a minim\'alna vzdialenos\v t medzi vrcholmi a
neincidentn\'ymi hranami (Obr\'azok \ref{fig:pravidla})
\end{itemize}
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/pravidla.eps}
\caption{Pravidl\'a pri kreslen\'i grafov}
\label{fig:pravidla}
\end{center}
\end{figure}
%!
%!
Pri kreslen\'i grafov sa takisto db\'a na r\^ozne estetick\'e
krit\'eri\'a, pri\v com niektor\'e z nich je ve\v lmi \v ta\v zko
zmera\v t (napr. symetria). Ak sa prihliada na viacero
krit\'eri\'i naraz, tak je ve\v lmi \v ta\v zk\'e dan\'y graf
pod\v la nich nakresli\v t, zvy\v cajne sa dar\'i dodr\v ziava\v t
jedno viac na \'ukor ostatn\'ych. Tak isto z\'ale\v z\'i aj
na tom, k \v comu bude v\'ysledn\'e nakreslenie pou\v zit\'e, a
pod\v la toho sa zvol\'i jedno, \v ci viac krit\'eri\'i, na ktor\'e
sa bude prihliada\v t. Najpou\v z\'ivanej\v sie krit\'eri\'a~:
\begin{itemize}
\item Maxim\'alna symetria
\item Predch\'adzanie kr\'i\v zeniu hr\'an
\item Predch\'adzanie ohybom hr\'an (polyline, orthogonal)
\item Zachova\v t jednotn\'u d\'l\v zku hr\'an
\item Rozvrhn\'u\v t vrcholy rovnomerne
\item Maxim\'alny sklon v ohyboch (polyline)
\item Maxim\'alny najmen\v s\'i uhol (straight-line, polyline)
\item Maxim\'alna vzdialenos\v t medzi vrcholmi pri danej ve\v lkosti n\'akresu
\end{itemize}
%!
%!!!! MOZNO NEJAKY OBRAZOK !!!
%!
\section{Z\'akladn\'e algoritmy a probl\'emy}
%!
%!
%! NP-uplne problemy
%!
%!
V kreslen\'i grafov je planarita ve\v lmi d\^ole\v zit\'a, vyu\v
z\'iva sa tak pri testovan\'i \v ci je dan\'y graf plan\'arny, ako
aj pri v\v seobecn\'ych met\'odach kreslenia grafov. Nane\v
stastie ve\v la probl\'emov spojen\'ych s planaritou s\'u
NP-\'upln\'e alebo NP-\v ta\v zk\'e :
\begin{itemize}
\item Rozhodn\'u\v t, \v ci pre pevn\'e $k$ sa po zmazan\'i
$k$-vrcholov stane graf plan\'arnym, je NP-\'upln\'y probl\'em
(Lewis a Yannakakis, 1980)
%!
\item Rozhodn\'u\v t, \v ci pre dan\'y graf a pevn\'e $k$ existuje
plan\'arny podgraf, ktor\'y m\'a aspo\v n $k$ hr\'an, je
NP-\'upln\'y probl\'em (Yannakakis, 1978)
%!
%! \pouzivam cast1\gt-upt-95.ps   str.17   -> mam v literature 
\item Testovanie upward planarity orientovan\'ych grafov je
NP-\'upln\'y probl\'em
%!\footnote{Zdroj je v ~\cite{tam3}} 
(Garg a Tamassia, 1995)
%!
%! toto je v \pouzivam cast1\draw.doc  -> ale nie je tam odkaz kde to je dokazane
\item N\'ajdenie maxim\'alneho plan\'arneho podgrafu je NP-\v ta\v
zk\'y probl\'em\footnote{Heuristika s dobr\'ymi v\'ysledkami na n\'ajdenie maxim\'alneho plan\'arneho podgrafu sa 
nach\'adza v~\cite{mutzel3}.}
\end{itemize}
%!
%!
Aj ve\v la vec\'i, ktor\'e sa t\'ykaj\'u krit\'eri\'i dobr\'eho
nakreslenia grafu, ako minimaliz\'acia kr\'i\v zen\'i alebo ohybov
a \v dal\v sie s\'u NP-\'upln\'e a NP-\v ta\v zk\'e probl\'emy~:
\begin{itemize}
\item Rozhodn\'u\v t, \v ci graf G m\^o\v zeme nakresli\v t s
maxim\'alne $k$ kr\'i\v zeniami, je NP-\'upln\'y probl\'em (Garey a Johnson, 1983)
%!
%! toto je v \pouzivam cast1\draw.doc  -> ale nie je tam odkaz kde to je dokazane
\item Nakresli\v t plan\'arny graf ortogon\'alne tak, aby mal
\v co najmenej ohybov je NP-\v ta\v zk\'y probl\'em\footnote{Zdroj pre tento probl\'em je v~\cite{sim}.}
%!
%! zdroj pre tieto je  \teraz\graphdraw.pdf
\item Minimalizovanie ve\v lkosti n\'akresu do mrie\v zky je NP-\v
ta\v zk\'y probl\'em\\(Kramer a Van Leeuwen, 1984)
%!
\item Minimalizovanie d\'l\v zky najdlh\v sej hrany je NP-\v ta\v
zk\'y probl\'em (Miller a Orlin, 1984)
\end{itemize}
%!
%!
Aj v kreslen\'i grafov existuj\'u otvoren\'e probl\'emy, niektor\'e z nich m\^o\v zeme n\'ajs\v t v~\cite{bran},~\cite{tam1}
alebo v~\cite{liter}. Existuj\'u aj \v specializovan\'e www str\'anky, ktor\'e sa zaoberaj\'u otvoren\'ymi probl\'emami v
graph drawingu, napr.~\cite{link1} alebo~\cite{link2}. Niektor\'e zauj\'imav\'e otvoren\'e probl\'emy v graph drawingu~:
\begin{itemize}
%!
%! zdroj pre toto dole www.graphdrawing.org
\item Dan\'y je neozna\v cen\'y plan\'arny graf s $n$ vrcholmi a
mno\v zina $n$ bodov v rovine. Chceme priradi\v t vrcholy k bodom tak,
aby sme vytvorili plan\'arny straight-line n\'akres. Ak\'a je
v\'ypo\v ctov\'a zlo\v zitos\v t tohoto probl\'emu?
%!
%! zdroj pre toto dole http://maven.smith.edu/~orourke/TOPP/Welcome.html
%!
\item M\'a ka\v zd\'y graf s maxim\'alnym stup\v nom vrchola $
\Delta \leq 6$ 3D orthogonal drawing, ktor\'y nem\'a viac ako dva
ohyby na hranu?
%!
%! zdroj pre toto dole \teraz\GraphDrawing02-Mel.ppt
%!
\item Ktor\'e z plan\'arnych grafov maj\'u $O(n)$ ve\v lkos\v t
n\'akresu pri straight-line drawingu? ($O(n^2)$ maj\'u v\v setky)
%!
\item Doln\'e ohrani\v cenie pre ve\v lkos\v t n\'akresu a ohyby v 
orthogonal drawingu neplan\'arnych grafov
\end{itemize}
%! niekolko otvorenych problemov je v /presiel/dobre/literatura/literatura.pdf , str.35,
%! ale to je z roku 1994
%!
%!
%! zname algoritmy !!!
%! v dokumente /pouzivam cast1/t-gd-97.ps je vela znamich algoritmov
%! a otvorenych problemov          - treba ich zhrnut do nejakej
%! prehladnej tabulky
%! !!! toto je velmi dolezite
%!
%!Zn\'ame algoritmy :
%!\begin{itemize}
%! \algoritmy\HandbookTR.ps
%! strana 5, je tam odkaz na knihy, kde to je
%!\item Polynomi\'alny algoritmus, ktor\'y graf $G$ s $n$ vrcholmi a pevn\'ym stup\v nom nakresl\'i
%!s maxim\'alne $O((v(G)+n)\log^{2} n)$ kr\'i\v zeniami (Bhatt, Leighton)
%!\end{itemize}
%!
%!
