\documentclass{beamer}
\usepackage[latin2]{inputenc}
\usepackage[czech]{babel}
\usepackage{palatino}
\usetheme{Warsaw}
\title[Kreslení grafů do roviny]{Kreslení grafů do roviny}
\author[Martin Mareš]{Martin Mareš\\\texttt{mj@ucw.cz}}
\institute{Charles University in Prague\\Faculty of Math and Physics\\Department of Applied Mathematics}
\date{}
\begin{document}
\setbeamertemplate{navigation symbols}{}
\setbeamerfont{title page}{family=\rmfamily}

\begin{frame}{Stavy vrcholů}

Při kreslení vrcholu~$v$ budeme označovat vrcholy v~už nakreslené
části takto:

~

\begin{itemize}

\item
Vrchol~$w$ je {\bf vnější,} pokud z~něj vede zpětná hrana do~ještě
nenakreslené části grafu (\uv{nad $v$}), nebo pokud je akrtikulací,
pod níž je připojen podgraf obsahující takový vrchol.

\item
Vrchol~$w$ je {\bf živý,} pokud z~něj vede zpětná hrana do~$v$.

\item
Podobně pro bloky (podle kořene) a zpětné hrany.

\end{itemize}

\end{frame}

\begin{frame}{Pravidla obcházení}

{\bf P1:}
V~každém živém vrcholu zpracováváme:
\begin{enumerate}
\item zpětné hrany do~$v$
\item podřízené živé vnitřní bloky
\item podřízené živé vnější bloky
\end{enumerate}

~

{\bf P2:}
Vstoupíme-li do podřízeného bloku, vybereme si směr:
\begin{enumerate}
\item k~živému vnitřnímu vrcholu
\item k~živému vnějšímu vrcholu
\end{enumerate}

Pokud se tento směr liší od~dosavadního, podřízený blok a vše pod ním
překlopíme.

\end{frame}

\begin{frame}{Algoritmus}

\begin{enumerate}
\item Pokud má graf více než $3n-6$ hran $\Rightarrow$ {\sc nerovinný.}
\item Prohledáme graf do hloubky: {\it Enter, Ancestor, LowPoint.}
\item<3-> Sestrojíme {\it BlockList}y a setřídíme je.
\item Pro vrcholy~$v$ v~pořadí klesajících {\it Enter\/}ů kreslíme:
\item Nakreslíme stromové hrany z~$v$ dolů jako triviální bloky (2-cykly).
\advance\leftskip by 2em
\item<4-> Označíme živý podgraf.
\item Pro každého syna vrcholu~$v$ obcházíme hranici v~obou směrech
      a kreslíme zpětné hrany do~$v$. Řídíme se pravidly {\bf P1} a {\bf P2,}
      za vnějším vrcholem se zastavíme.
\item Zbývá-li nějaká zpětná hrana do~$v$ $\Rightarrow$ {\sc nerovinný.}

\advance\leftskip by -2em
\item<2-> Zorientujeme seznamy sousedů $\Rightarrow$ hotové nakreslení.
\end{enumerate}

\end{frame}

\end{document}
