From 0c7c015ec8c92d2fd896bdb4ce70f25a93480ff8 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 10 Jan 2019 09:34:17 +0100
Subject: [PATCH] =?utf8?q?Slidy=20k=20rovinn=C3=A9mu=20kreslen=C3=AD=20maj?=
 =?utf8?q?=C3=AD=20i=20anglickou=20verzi?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 11-planar/slides/Makefile                     |  6 +-
 .../slides/{planar.tex => planar-cs.tex}      |  2 +-
 11-planar/slides/planar-en.tex                | 83 +++++++++++++++++++
 3 files changed, 88 insertions(+), 3 deletions(-)
 rename 11-planar/slides/{planar.tex => planar-cs.tex} (98%)
 create mode 100644 11-planar/slides/planar-en.tex

diff --git a/11-planar/slides/Makefile b/11-planar/slides/Makefile
index c602f59..bbc4d6c 100644
--- a/11-planar/slides/Makefile
+++ b/11-planar/slides/Makefile
@@ -1,5 +1,7 @@
-all:
-	pdflatex planar.tex
+all: planar-cs.pdf planar-en.pdf
+
+%.pdf: %.tex
+	pdflatex $<
 
 clean:
 	rm -f *.{aux,log,nav,out,pdf,snm,toc}
diff --git a/11-planar/slides/planar.tex b/11-planar/slides/planar-cs.tex
similarity index 98%
rename from 11-planar/slides/planar.tex
rename to 11-planar/slides/planar-cs.tex
index 9d53f61..c82fbec 100644
--- a/11-planar/slides/planar.tex
+++ b/11-planar/slides/planar-cs.tex
@@ -1,5 +1,5 @@
 \documentclass{beamer}
-\usepackage[latin2]{inputenc}
+\usepackage[utf8]{inputenc}
 \usepackage[czech]{babel}
 \usepackage{palatino}
 \usetheme{Warsaw}
diff --git a/11-planar/slides/planar-en.tex b/11-planar/slides/planar-en.tex
new file mode 100644
index 0000000..e7c1669
--- /dev/null
+++ b/11-planar/slides/planar-en.tex
@@ -0,0 +1,83 @@
+\documentclass{beamer}
+\usepackage[utf8]{inputenc}
+\usepackage{palatino}
+\usetheme{Warsaw}
+\title[Planar embedding of graphs]{Planar embedding of graphs}
+\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}{Vertex states}
+
+When embedding a~vertex~$v$, we will classify already embedded vertices
+as follows:
+
+~
+
+\begin{itemize}
+
+\item
+A~vertex~$w$ is {\bf external,} if it has a~back edge to a~not-yet-embedded
+ancestor (``above~$v$''), or if it is an~articulation point with a~subordinate
+block containing an~external vertex. All other vertices are {\bf internal.}
+
+\item
+A~vertex~$w$ is {\bf live,} if it has a~back edge to~$v$ or if it has
+a~subordinate block containing a~live vertex.
+
+\item
+Similarly for blocks (by their roots) and back edges.
+
+\end{itemize}
+
+\end{frame}
+
+\begin{frame}{Walking rules}
+
+{\bf R1:}
+In each live vertex, we process (in this order):
+\begin{enumerate}
+\item back edges to~$v$
+\item subordinate live internal blocks
+\item subordinate live external blocks
+\end{enumerate}
+
+~
+
+{\bf R2:}
+when we enter a~subordinate block, we choose the walking direction (in this order):
+\begin{enumerate}
+\item to a~live internal vertex
+\item to a~live external vertex
+\end{enumerate}
+
+If this direction differs from the present one, the subordinate block and all
+its descendant blocks will be flipped.
+
+\end{frame}
+
+\begin{frame}{The Boyer-Myrvold algorithm}
+
+\begin{enumerate}
+\item If the graph has more than $3n-6$ edges $\Rightarrow$ {\sc not planar.}
+\item Depth-first search on the graph: {\it Enter, Ancestor, LowPoint.}
+\item<3-> We construct {\it BlockList\/}s and sort them.
+\item We embed vertices~$v$ in order of decreasing {\it Enter\/}s:
+\item Embed tree edges from~$v$ down as trivial blocks (2-cycles):
+\advance\leftskip by 2em
+\item<4-> We mark the live subgraph.
+\item For each child of the vertex~$v$, we walk around the boundary in both directions
+      and we embed back edges to~$v$. We follow the rules {\bf R1} and {\bf R2.}
+      We stop when we visit an external vertex.
+\item If there remains any non-embedded back edge to~$v$ $\Rightarrow$ {\sc not planar.}
+
+\advance\leftskip by -2em
+\item<2-> We orient all lists of neighbors $\Rightarrow$ final embedding.
+\end{enumerate}
+
+\end{frame}
+
+\end{document}
-- 
2.39.2