\chapter{\'Uvod}
%!
%!
%!
\hyphenation{mo-no-t\'o-nne PERT ma-na-ge-ment dia-gra-my ap-li-ka-\v cno s\'u-bo-ro-v\'ych}
%!
%!
%!
Graf je abstraktn\'a \v strukt\'ura, ktor\'a je \v casto pou\v z\'ivan\'a na zobrazenie 
inform\'acie. Graf m\^o\v ze zobrazova\v t inform\'acie,
ktor\'e m\^o\v zu by\v t modelovan\'e ako objekty a spojenia medzi
t\'ymito objektami. Preto skoro ka\v zd\'a oblas\v t po\v c\'ita\v
covej vedy a softv\'erov\'eho priemyslu pou\v z\'iva grafy v
nejakej forme na reprezentovanie inform\'aci\'i.
\newline
\newline
%!
%!
%!
%! \pouzivam cast1\t-gd-97.ps     -> mam v literature !
%! obrazok typov kreslenia
%! posis jednotlivych typov kreslenia
%! na strane 8 su niektore otvorene problemy
%! strana 9 -> velmi dobra tabulak niektorych problemov -> treba doplnit sem do nizsej sekcie
%!
%! \citeseer1_200\tamassia96advances.ps          -> mam v literature !
%! obrazkok visibility,upward polyline drawing, str.9
%!
%!
%!
Graph drawing sa zaober\'a probl\'emom zobrazenia geometrickej
reprezent\'acie grafov. V\'yskum v graph drawingu pokra\v cuje v
nieko\v lk\'ych r\^oznych oblastiach, vr\'atane diskr\'etnej
matematiky (te\'oria grafov, geometrick\'a te\'oria grafov),
algoritmov (grafov\'e algoritmy, d\'atov\'e \v strukt\'ury,
v\'ypo\v ctov\'a geometria, VLSI) a interakcie \v clovek-po\v
c\'ita\v c (vizu\'alne jazyky, grafick\'y user interface,
softv\'erov\'a vizualiz\'acia).
\newline
\newline
%!
%!
%! http://graphml.graphdrawing.org/specification/index.html
%! je tam dokument na stiahnutie, ktory sa zaobera pokrokom v GraphML
%!
%!
%! http://graphml.graphdrawing.org/
%! mohla by sa dat poznamka pod ciarou s odkazom na toto a dokument
%!
%!
Existuje viacero programov, ktor\'e sl\'u\v zia na kreslenie,
vytv\'aranie a vizualiz\'aciu grafov. Skoro ka\v zd\'y z
t\'ychto programov pou\v z\'iva vlastn\'y form\'at s\'uborov na
pracovanie s grafmi. Pr\'ave preto sa na Graph Drawing Symposium
2000 vo Williamsburgu za\v cala pr\'aca na novom form\'ate
s\'uborov pre grafy, GraphML\footnote{Viac o form\'ate GraphML je v~\cite{graphML}.}. 
N\'avrh na \v strukturovan\' u vrstu
bol prezentovan\'y na Graph Drawing Symposium 2001 vo Viedni.
GraphML je obsiahly a jednoducho pou\v ziteln\' y s\'uborov\'y
form\'at, ktor\'y podporuje orientovan\'e grafy, neorientovan\'e
grafy, hypergrafy, hierarchick\'e grafy, grafick\'e
reprezent\'acie, referencie na extern\'e d\'ata, aplika\v cno \v
specifick\'e atrib\'utov\'e d\'ata a jednoduch\'e parsery. Na
rozdiel od in\'ych s\'uborov\'ych form\'atov pre grafy, GraphML
nepou\v z\'iva vlastn\'u syntax. Namiesto toho je zalo\v zen\'y na
XML a preto je ide\'alne vhodn\'y ako spolo\v cn\'y menovate\v l
pre v\v setky druhy funk\v cnost\'i, ako napr. vytv\'aranie,
archivovanie alebo pracovanie s grafmi.
\newline
\newline
%!
%!
V tejto pr\'aci sa budeme zaobrera\v t kreslen\'im grafov, ktor\'e
maj\'u vrcholy v dvoch skupin\'ach. V tejto kapitole uvedieme
z\'akladn\'e inform\'acie o kreslen\'i grafov, typy kreslenia a
aplik\'acie kreslenia grafov. V kapitole 2 pop\'i\v seme
z\'akladn\'e defin\'icie, pravidl\'a a krit\'eri\'a pri kreslen\'i
grafov, niektor\'e algoritmy, NP-\v ta\v zk\'e a NP-\'upln\'e
probl\'emy, niektor\'e otvoren\'e probl\'emy. V kapitole~3 uvedieme met\'ody kreslenia 
z\'akladn\'ych grafov ako s\'u stromy,
kompletn\'e grafy, plan\'arne grafy ako aj met\'ody kreslenia v\v
seobecn\'ych grafov. V kapitole~4 sa budeme zaobera\v t
dokres\v lovan\'im hr\'an a vrcholov do u\v z nakreslen\'eho grafu
(neorientovan\'y graf, straight-line drawing). Uvedieme dve nov\'e heuristiky na dokres\v lovanie vrcholov do grafu.
V kapitole 5 sa budeme venova\v t kresleniu grafov, ktor\'e maj\'u vrcholy v
dvoch skupin\'ach. \v Ziadna dostupn\'a literat\'ura sa probl\'emom kreslenia dvojfarebn\'ych grafov nezaoberala.
Bud\'u tam uveden\'e r\^ozne pr\'istupy na kreslenie tak\'ychto grafov, vr\'atane dvoch nov\'ych algoritmov 
zalo\v zen\'ych na dokres\v lovan\'i vrcholov.  
V kapitole 6 tieto pr\'istupy experiment\'alne porovn\'ame vzh\v ladom na zvolen\'u
metriku nakreslenia.
\newline
V pr\'ilohe bude kr\'atky manu\'al k implementovan\'emu programu na vytv\'aranie a kreslenie dvojfarebn\'ych 
grafov ako aj preh\v lad najhlavnej\v s\'ich implementovan\'ych funkci\'i v tomto programe. Bud\'u tam uveden\'e aj niektor\'e
probl\'emy, ktor\'e sa objavili po\v cas implement\'acie nad kni\v znicou algoritmov \texttt{LEDA} spolu s ich rie\v seniami. 
V poslednej \v casti pr\'ilohy bud\'u uk\'a\v zky r\^oznych nakreslen\'i grafov v implementovanom programe. T\'ato pr\'aca 
obsahuje aj CD-pr\'ilohu, na ktorej n\'ajdeme elektronick\'u verziu tejto diplomovej pr\'ace spolu s jej zdrojov\'ymi 
s\'ubormi, implementovan\'y program, jeho zdrojov\'e s\'ubory, v\'ysledky testov a 
obr\'azky nakreslenia r\^oznych grafov v tomto programe.
\newline
\newline
%!
%!
\section{Typy a aplik\'acie kreslenia grafov}
%!
%!
V kreslen\'i grafov sa vrcholy reprezentuj\'u ako body (alebo ako geometrick\'e \'utvary
napr.~kru\v znica alebo obd\'l\v znik) a hrany s\'u reprezentovan\'e krivkami tak, \v ze
ka\v zd\'e dve hrany sa pret\'inaj\'u najviac v kone\v cnom po\v cte bodov.
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.85\textwidth]{obrazky/2grafy.eps}
\caption{Dve r\^ozne nakreslenia toho ist\'eho grafu, z druh\'eho nakreslenia je vidie\v t, \v ze graf je plan\'arny
} \label{fig:kocka}
\end{center}
\end{figure}
%!
%!
\newline
\newline
Pri kreslen\'i grafov v 2D priestore sa pou\v z\'ivaj\'u r\^ozne
pr\'istupy kreslenia hr\'an a vrcholov, pod\v la toho k \v comu
sl\'u\v zi v\'ysledn\'e nakreslenie grafu. Niektor\'e z nich sa
daj\'u medzi sebou aj kombinova\v t (napr. polyline + planar
drawing) a niektor\'e sa daj\'u roz\v s\'iri\v t aj na 3D
priestor. Najpou\v z\'ivanej\v sie typy kreslenia grafov s\'u~:
%!
\begin{description}
\item[Straight-line drawing] -- ka\v zd\'a hrana je \'use\v cka
%!
\item[Polyline drawing] -- ka\v zd\'a hrana je reprezentovan\'a
lomenou \v ciarou (m\^o\v ze by\v t aj viac kr\'at lomen\'a)
%!
\item[Orthogonal drawing] -- ka\v zd\'a hrana je zre\v tazenie
horizont\'alnych a vertik\'alnych \'use\v ciek
%!
\item[Planar drawing] -- \v ziadne dve hrany sa nekri\v zuj\'u
%!
\item[Upward drawing] -- kreslenie orientovan\'eho grafu, kde ka\v
zd\'a hrana je monot\'onne neklesaj\'uca v smere osi $y$
%!
\item[Layered drawing] -- kreslenie vrstvov\'eho grafu tak, \v ze
vrcholy patriace tej istej vrstve le\v zia na rovnakej
horizont\'alnej \v ciare (taktie\v z naz\'yvan\'e hierarchical
drawing)
%!
\item[Visibility drawing] --
kreslenie grafu zalo\v zen\'e na geometrickej vidite\v lnosti,
napr.~vrcholy mo\v zu byt kreslen\'e ako horizont\'alne \'useky a
hrany s\'u vertik\'alne vidite\v ln\'e \v casti
%!
\item[Dominance drawing] -- upward drawing acyklick\'eho orientovan\'eho grafu, kde cesta z vrcholu $u$ do 
vrcholu $v$ existuje vtedy a len
vtedy, ak s\'u s\'uradnice vrchola $v$ v\"a\v c\v sie ako
s\'uradnice vrchola $u$ (teda $x(u) \leq x(v)$ a $y(u) \leq y(v)$)
\end{description}
%!
%!
\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/typy.eps}
\caption{Typy kreslenia: (a) polyline drawing $K_{3,3}$ (b) straight-line drawing $K_{3,3}$
(c) orthogonal drawing $K_{3,3}$ (d) planar upward drawing acyklick\'eho orientovan\'eho grafu}
\label{fig:typy}
\end{center}
\end{figure}
%!
%!
Straight-line a orthogonal kreslenia s\'u \v speci\'alnym typom polyline kreslenia. Polyline
kreslenie poskytuje ve\v lk\'u flexibilitu, preto\v ze m\^o\v ze zobrazova\v t hrany ako
aproximovan\'e krivky. Av\v sak, hrany s viac ako dvoma alebo troma ohybmi m\^o\v zu by\v t
\v ta\v zk\'e na sledovanie okom. Taktie\v z syst\'em, ktor\'y funguje na polyline kreslen\'i je
ove\v la komplikovanej\v s\'i ako syst\'em zalo\v zen\'y na straight-line kreslen\'i.
Preto z\'ale\v z\'i na jednotliv\'ych aplik\'aci\'ach, \v ci je preferovan\'e polyline alebo
straight-line kreslenie. Ke\v d s\'u vrcholy reprezentovan\'e bodmi, tak ortogonal kreslenie
je mo\v zn\'e iba pre grafy s maxim\'alnym stup\v nom vrchola \v styri.
\newline
\newline
%!
%!
Vizualiz\'acia komplexn\'ych \v strukt\'ur je k\v l\'u\v covou zlo\v zkou podpory n\'astrojov
pre ve\v la aplik\'aci\'i vo vede a in\v zinierstve. Napr\'iklad softv\'erov\'e in\v zinierstvo
(call graphs, class hierarchies), datab\'azov\'e syst\'emy (entity-relationship diagramy),
digit\'alne kni\v znice, World Wide Web browsovanie (hypermedi\'alne dokumenty), distribuovan\'e
po\v c\'itanie, VLSI (symbolick\'e v\'ypo\v cty), elektronick\'e syst\'emy (block diagramy,
circuit schematics), projekt management (diagramy PERT, organization charts), medic\'ina
(concept lattices), telekomunik\'acie (pokrytie telef\'onnych siet\'i), pr\'avo (conceptual
nets).
\newline
\newline
Najd\^ole\v zitej\v sie aplik\'acie kreslenia grafov :
\begin{itemize}
\item Software engineering (hierarchie classov)
%!
\item Datab\'azov\'e syst\'emy (ER-diagramy)
%!
\item Projekt management (PERT diagramy)
%!
\item Reprezent\'acia znalost\'i (isa hierarchie)
%!
\item Telekomunik\'acie (pokrytie telef\'onov)
%!
\item www (browsing history)
\end{itemize}
Navy\v se okrem hore zmienen\'ych oblast\'i sa grafy pou\v
z\'ivaj\'u na zobrazovanie inform\'aci\'i v aplik\'aci\'ach pre
kompil\'atory, in\v zinierstvo a CAD, paraleln\'e architekt\'ury,
informa\v cn\'y mana\v zment, siete a syst\'emov\'y mana\v zment,
mana\v zment finan\v cn\'ych transakci\'i, objektovo orientovan\'a
anal\'yza/design, modelovanie siet\'i chemick\'ych reakci\'i a v
mnoh\'ych in\'ych aplik\'aci\'ach.
%!
%!\newline
%!\newline
%! sociologiu asi vynecham
%! Sociol\'ogia - soci\'alna sie\v tov\'a te\'oria, zaoberaj\'uca sa vz\'ajomn\'ym p\^osoben\'im
%! jedincov a skup\'in pomocou analyzovania diagramu ich spojenia. Tieto diagramy s\'u \v casto
%! reprezentovan\'e ako grafy, preto kreslenie grafov je d\^ole\v zit\'y faktor v pochopen\'i
%! t\'ychto diagramov.
%!
%!
