% This is the revised version of that submitted to Electronic
% Journal of Combinatorics on September 15, 1998.
% Date: October 1, 1998
% If this paper is compiled from the LaTeX2e source file supplied,
% it will produce PS and PDF files suitable for color viewing and
% printing. The PS and PDF files that are posted in the Journal
% are color files.
% 
% If the reader does not have color printing and/or viewing capability,
% the source file should be modified to produce files suitable for
% B-W printing/viewing. This is very easy. Edit the LaTeX source file.
% Near the top of the file is a line "\setcounter{BlackWhite}{0}".
% Just change the {0} to {1}, and compile the file normally. The result
% will be that you will obtain PS and PDF files that are optimized for
% B-W printing.



\documentclass[12pt,fleqn]{article}

\newcounter{BlackWhite}     % 0 = Colour,   1 = Black and White
\setcounter{BlackWhite}{0}

\pagestyle{myheadings}
  \markright{\sc the electronic journal of combinatorics 5 (1998), \#R44\hfill}
  \thispagestyle{empty}

\usepackage{lscape}
\usepackage{ifthen}
% \usepackage{euler}
% \usepackage{beton}
\usepackage{latexsym}
\usepackage{epsfig}

\newtheorem{theorem}{{\bf Theorem}}[section]
\newtheorem{lemma}{{\bf Lemma}}[section]
\newtheorem{corollary}[theorem]{{\bf Corollary}}
\newtheorem{definition}{{\bf Definition}}[section]
\newtheorem{conjecture}{{\bf Conjecture}}[section]

\setlength{\oddsidemargin}{0.20in}
\setlength{\evensidemargin}{0.20in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6in}

\title{Venn Diagrams with Few Vertices}
\author{ {\sc Bette Bultena} and {\sc Frank Ruskey} \\
     {\small \texttt{ abultena@csr.csc.uvic.ca },
             \texttt{ fruskey@csr.csc.uvic.ca} } \\
     {\small \em Department of Computer Science} \\
     {\small \em University of Victoria} \\
     {\small \em Victoria, B.C. V8W 3P6, Canada} \\
     {\small Submitted: September 15, 1998, Accepted: October 1, 1998 } }

% \date{\today}
\date{\empty}

\begin{document}

\maketitle

\begin{abstract}
An {\em $n$-Venn diagram} is a collection of $n$ finitely-intersecting
  simple closed curves in the plane, such that each of the $2^n$ sets
  $X_1 \cap X_2 \cap \cdots \cap X_n$, where each $X_i$ is the open
  interior or exterior of the $i$-th curve, is a non-empty
  connected region.
The \emph{weight} of a region is the number of curves that contain it.
A region of weight $k$ is a $k$-region.
A {\em monotone} Venn diagram with $n$ curves has the property that every
  $k$-region, where $0<k<n$, is adjacent to at least one $(k-1)$-region
  and at least one $(k+1)$-region.
Monotone diagrams are precisely those that can be drawn with all
  curves convex.

An $n$-Venn diagram can be interpreted as a planar graph in which
  the intersection points of the curves are the vertices.
For general Venn diagrams, the number of vertices
  is at least $ \lceil \frac{2^n-2}{n-1} \rceil$.
Examples are given that demonstrate that this bound can be
  attained for $1 < n \le 7$.
We show that each monotone Venn diagram has at least
  ${n \choose {\lfloor n/2 \rfloor}}$ vertices, and that this
  lower bound can be attained for all $n > 1$.
\end{abstract}

\noindent
\textbf{Keywords:} Venn diagram, dual graph, convex curve, Catalan number. \\
\textbf{AMS Classification (primary, secondary):} 05C10, 52C99.

\section{Introduction}

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{venn3exBW.pstex_t} }
  { \input{venn3ex.pstex_t} }
\end{center}
\caption{Example of a simple and a non-simple 3-Venn diagram.}
\label{fig:ex3}
\end{figure}

There has been a renewed interest in Venn diagrams in the
  past couple of years.
Recent surveys have been written by Ruskey~\cite{Ruskey} and
  Hamburger~\cite{Ha98}.
In this paper we tackle a natural problem that has not
  received any attention:
What is the least number of vertices in a Venn diagram
  of $n$ curves?
Figure~\ref{fig:ex3}(a) shows the classic Venn diagram of $3$ curves,
  which contains $6$ vertices.
The Venn diagram of Figure~\ref{fig:ex3}(b) is also constructed with
  $3$ curves, but has only $3$ vertices.
This second diagram has the minimum number of vertices among all Venn
  diagrams of $3$ curves (a complete listing may be found in
  Chilakamarri, Hamburger, and Pippert~\cite{CHP2}).
We show that this is the minimum value in Theorem~\ref{thm:absMin}
  in the following section.

We give the relevant graph theoretic definitions in the
  remainder of this section.
Section 2 provides a proof of the lower bound for the number of
  vertices of general Venn diagrams and provides examples of Venn
  diagrams that have this minimum number if $1 < n \le 7$.
Finding a minimum vertex Venn diagram for $n > 7$ remains
  an open problem.
In Section 3, we demonstrate that the upper bound of
  ${n \choose {n/2}}$ for the minimum number of vertices of a
  monotone Venn diagrams is attainable for all $n > 1$.
This is demonstrated, using a specific and recursively constructed
  sequence of diagrams.
The proof that the number of vertices is as stated
  involves the Catalan numbers.

\subsection{Venn Diagrams and Graphs}

Let us review Gr\"{u}nbaum's definition of a Venn diagram~\cite{Grun}.
An {\em $n$-Venn diagram} in the plane is a collection of simple closed
  Jordan curves $ {\mathbf C} = {C_1, C_2, \dots, C_n}$, such that
  each of the $2^n$ sets $X_1 \cap X_2 \cap \ldots \cap X_n$
  is a nonempty and connected region.
Each $X_i$ is either the bounded interior or the unbounded exterior of
  $C_i$, and this intersection can be uniquely identified by a
  subset of $\{1,2,\ldots,n\}$, indicating the subset of the indices of
  the curves whose interiors are included in the intersection.
To this definition we add the condition that
  pairs of curves can intersect only at a finite number of points.

We say that two Venn diagrams are \emph{isomorphic} if, by continuous
  transformation of the plane, one of them can be changed into
  the other or its mirror image~\cite{Ruskey}.

When analyzing a Venn diagram, we often think of it as a plane graph
  $V$, whose vertices (called Venn vertices) are the intersection points
  of the curves.
The labelled edges of $V$ are of the form $C(v,w)$, where there is
  a segment on curve $C$ with intersection points $v$ and $w$, and
  no intersection points between them on $C$.
The label of the edge is $i$ if $C = C_i$.
Each face, including the outer infinite face, is called a {\em region}
  when referring to $V$.
Each region in the Venn diagram has associated with it a unique
  subset of ${1,2, \ldots, n}$, and a \emph{weight}.
The weight is the number of curves that contain the region and
  is equal to the cardinality of its representative subset.
A region of weight $k$ is referred to as a $k$-region.

A facial walk of a region is a walk taken around the region
  in clockwise order, recording the edges and vertices bordering the region
  as they are encountered.
It is easy to prove that the graph $V$ is 2-connected, and hence
  each edge borders exactly two regions.
Both vertices of this edge are found on facial walks of both regions.
A \emph{vertex traversal} of a vertex $v$ in a Venn diagram is a
  circular sequence $C_0, C_1, \ldots , C_m$ of the curves adjacent
  to $v$, when read in a clockwise rotation around $v$~\cite{Ruskey}.

We also use the familiar dual graph, $D(V)$, of the Venn diagram.
It is constructed by placing a vertex within each region of $V$.
For each edge of $V$, a dual graph edge is drawn which connects
  the vertices within the two adjacent regions.
Note that each of the {\em dual vertices} corresponds to a face in $V$,
  and each of the {\em Venn vertices} corresponds to a face in $D(V)$.
We identify each of the dual vertices by the same subset and weight of
  the associated region on $V$.
We define the \emph{directed} dual graph, $\vec{D}(V)$, by imposing a
  direction on each edge so that it is directed from the vertex of larger weight
  to the vertex of smaller weight~\cite{Ruskey}.

The vertex set of the {\em radual graph} $R(V)$ consists of the union
  of the vertex sets of $V$ and $D(V)$.
The edge set of $R(V)$ consists of all edges in $D(V)$ together
  with edges between each dual vertex and the following specified Venn
  vertices:
In the radual graph, a dual vertex $d$ is adjacent to a Venn vertex
  $v$ if $v$ is encountered on a facial walk around the region of
  $V$ containing $d$.
The radual graph construction is illustrated in Figure \ref{fig:radual}.
The radual graph of any 2-connected planar graph is itself planar.
Note that the edges incident with $d$ in $R(V)$ are alternately
  incident with Venn vertices and dual vertices as we circle around
  $d$ in a fixed direction.

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{dualRadBW.pstex_t} }
  { \input{dualRad.pstex_t} }
\end{center}
\caption{The radual graph construction.}
\label{fig:radual}
\end{figure}

\subsection{Monotone Venn Diagrams}

In this paper we are primarily interested in those Venn diagrams that
  are monotone.
Following~\cite{Ruskey}, we define a diagram to be \emph{monotone}
  if and only if the {\em directed} dual graph $\vec{D}(V)$ has a
  unique sink (a vertex with no out-going edges), and a unique
  source (a vertex with no incoming edges).
An equivalent definition of a monotone Venn diagram is that
  each dual vertex with weight $0 < k < n$ in the dual graph is
  adjacent to a dual vertex with weight $k-1$ and a dual vertex
  with weight $k+1$.

Monotone diagrams are a natural and interesting class of Venn diagrams.
The general constructions of Edwards~\cite{Edwards1},~\cite{Edwards2}
  are monotone.
The ``necklace property'' mentioned in Edwards~\cite{Edwards} is a
  consequence of monotonicity.
A Venn diagram is \emph{convex} if its curves are convex.
The Venn diagrams in Figure~\ref{fig:ex3} are both convex.
In~\cite{BuRuGr}, it is proven that a Venn diagram is isomorphic to a
  convex Venn diagram if and only if it is monotone.
Thus the geometric condition of convexity is equivalent to the
  purely combinatorial condition of monotonicity.

\section{General Venn Diagrams}

Let $Min(n)$ be the least number of vertices of a Venn diagram of
  $n$ curves.

\begin{theorem}
If $n>1$, then
\[
  Min(n) \ge \left\lceil \frac{2^n-2}{n-1} \right\rceil \mbox{.}
\]
\label{thm:absMin}
\end{theorem}

\noindent
\textbf{Proof:}
Consider a $n$-Venn diagram $V$, with vertex set $W$.
Let $f$, $v$, and $e$ denote the number of faces, vertices and edges
  of $V$.
We denote the degree of vertex $w$ as $deg(w)$.
By definition, for $w \in W$, $deg(w)$ is no more than $2n$.
So
\[
2nv \ge \sum_{w \in W}{deg(w)} = 2e.
\]
By Euler's relation, $e = 2^n+v-2$, and
therefore
\[
v \ge \frac{2^n-2}{n-1} \mbox{.}
\]
\hfill $\Box$

\vspace{\baselineskip}

We provide examples of general $n$-Venn diagrams that attain this
  lower bound for $1 < n \le 7$.
Figure~\ref{fig:minFour} shows a minimum $4$-Venn discovered in
  collaboration with Peter Hamburger.
Figure~\ref{fig:minFive} and \ref{fig:minSix} are diagrams which
  are successively extended from the minimum $4$-Venn diagram, discovered
  by the first author.

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{betteMin4BW.pstex_t} }
  { \input{betteMin4.pstex_t} }
\end{center}
\caption{A $4$-Venn diagram with $5$ vertices.}
\label{fig:minFour}
\end{figure}

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{betteMin5BW.pstex_t} }
  { \input{betteMin5.pstex_t} }
\end{center}
\caption{A $5$-Venn diagram with $8$ vertices.}
\label{fig:minFive}
\end{figure}

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{min6BW.pstex_t} }
  { \input{min6.pstex_t} }
\end{center}
\caption{A $6$-Venn diagram with $13$ vertices.}
\label{fig:minSix}
\end{figure}

\begin {figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{min7singleBW.pstex_t} }
  { \input{min7single.pstex_t} }
\end{center}
\caption{A $7$-Venn diagram with $14$ vertices.}
\label{fig:minSeven}
\end{figure}

Figure~\ref{fig:minSeven} is a polar symmetric minimum $7$-Venn
  diagram, discovered in collaboration with Stirling Chow
  using a computer search.
Note that each vertex has the maximum degree; every
  curve passes through every vertex.
The diagram is symmetric in the sense that each curve of the diagram
  can be obtained by rotating a given curve (e.g., the highlighted
  one in the diagram) by a multiple of $2\pi/7$ about some
  point on the plane.
Symmetric diagrams in this sense can only exist if $n$ is prime.
Thus a minimum vertex symmetric diagram might only exist if
  $n$ is a prime for which $n-1$ divides $2^n-2$.
The only such primes, $7<n<100$, are 19 and 43.

The diagrams of this section inspire the conjecture that the lower
  bound of Theorem \ref{thm:absMin} can be achieved for all numbers $n$.
We leave this as an open problem.

\section{Monotone Venn Diagrams}
The following lemmas deal with general plane graphs, illustrating
  that each dual vertex in the radual graph is bordered by a
  specific type of cycle.
The lemmas are used to prove the lower bound for monotone Venn
  diagrams.

\begin{lemma}
The degree of a dual vertex $d$ in the radual graph is equal to twice the
  number of edges on the facial walk of the region containing $d$
  in the original plane graph.
\label{lem:spokes}
\end{lemma}

\noindent \textbf{Proof:}
Consider $P$, $D(P)$, and $R(P)$, a plane graph, its dual graph, and
  its radual graph, respectively:
Let $d$ be a dual vertex within face $F$ of $P$.
There are an equal number of edges and vertices on the facial
  cycle of $F$.
Each vertex $v_i$ on this cycle is adjacent to $d$ by definition
  of $R(P)$.
Each edge on the facial cycle of $F$ corresponds to an edge
  between $d$ and another dual vertex $d_i$ in region $S$ of
  $P$.
Therefore $d$ is adjacent to the total number of vertices
  and edges on $F$'s facial cycle.
\hfill $\Box$

\begin{lemma}
The subgraph of the radual graph $R(P)$ induced by the open
  neighbourhood of a dual vertex $d$ is an alternating
  cycle of dual vertices and vertices of the plane graph $P$.
\label{lem:wheel}
\end{lemma}

\noindent \textbf{Proof:}
Choose any $2$ {\em consecutive} (in a small circle around $d$)
  vertices $v$ and $w$ that are adjacent to $d$ in $R(P)$.
Without loss of generality, let $v$ be a vertex of $P$ and
  $w$ a dual vertex in the region $S$ of $P$.
Then $v$ is also contained on the facial cycle of $S$ and
  therefore is adjacent to $w$.
\hfill $\Box$

\vspace{\baselineskip}

An interesting property of monotone Venn diagrams is that they can
  be {\em peeled}.
For an $n$-Venn diagram $V$ and an integer $k \ge 1$, the $k$-peeled
  subgraph $V_k$ of $V$ is obtained by first removing all edges
  that border two regions in $V$ of weights less than $k$,
  and then removing all isolated vertices.

\begin{lemma}
A $k$-peeled subgraph $V_k$ of a monotone $n$-Venn $V$ contains every
  original region whose weight is at least $k$, and no bounded regions
  of weight less than $k$.
\label{lem:Borg}
\end{lemma}

\noindent \textbf{Proof} (by induction on $k$):
For the base case observe that $V_1$ is the same as $V$.

For $k \ge 1$, assume the statement is true.
Consider $V_k$, the $k$-peeled graph of a monotone $n$-Venn diagram $V$,
  and its original dual graph $D(V)$.

Each dual vertex with weight $k$ is connected to at least one dual vertex
  of weight $k-1$, by the definition of a monotone Venn diagram.
By the induction hypothesis, each dual vertex with weight $k$ is contained
  in a closed region of $V_k$, while each weight $k-1$ dual vertex is
  located in the unbounded region of $V_k$.
By definition of the dual graph, there is an edge in the Venn diagram
  that corresponds to each dual graph edge between two dual vertices
  of weights $k-1$ and $k$.
The removal of each of these Venn edges, peels $V_k$ and opens each
  $k$-region to the outer unbounded region.

None of the regions with weight greater than $k$ are affected.
No $k$-region is left bounded in the peeled graph.
Therefore the statement is true for $V_{k+1}$.
\hfill $\Box$

\vspace{\baselineskip}

Using the same steps as in the construction of the radual graph of
  an $n$-Venn diagram, we construct the radual graph of a $k$-peeled
  graph of a monotone $n$-Venn diagram.
Note that if we remove the dual vertex associated with the unbound
  region, we have a subgraph of the radual graph associated with
  the original monotone $n$-Venn diagram.

\begin{theorem}
For any radual graph $R(V)$, of a monotone $n$-Venn diagram $V$,
  and any $0 < k < n$, there is a cycle of size $2{n \choose k}$ in $R(V)$,
  consisting of alternating Venn vertices and dual vertices with weight $k$.
\label{thm:cycles}
\end{theorem}

\noindent \textbf{Proof:}
Consider $V_k$, the $k$-peeled graph of an $n$-Venn diagram $V$.
By Lemma~\ref{lem:Borg}, there are no regions with weight $k-1$ within $V_k$.
Therefore, all weight $k-1$ regions of $V$ are part of the unbounded
  region in $V_k$.
Since all the weight $k$ regions in $V_k$ must share an edge with regions
  with weight $k-1$, there are ${n \choose k}$ outer edges on $V_k$.

Now consider the radual graph, $R(V_k)$:
Let $d$ be the dual vertex in $R(V_k)$ of the unbounded region in $V_k$.
By Lemma~\ref{lem:spokes}, $deg(d) = 2{n \choose k}$, and by
  Lemma~\ref{lem:wheel}, the vertices adjacent to $d$ form a cycle
  which alternates between Venn vertices and dual vertices with weight $k$.
Since neither $d$ nor any of its edges are involved, this cycle
  is contained in the subgraph of $R(V)$.
\hfill $\Box$

\vspace{\baselineskip}

Let $M_n$ be the minimum number of vertices in a monotone $n$-Venn diagram.
To prove that $M_n = {n \choose {\lfloor n/2 \rfloor}}$, we first show
  this is a lower bound, and then show that this value is attained
  by a certain sequence of Venn diagrams.
We obtain the lower bound of $M_n$ from the number of ($n/2$)-subsets of
  $\{1, 2, \ldots ,n\}$.

\begin{theorem}
If $n > 1$, then
\[ M_n \ge {n \choose {\lfloor n/2 \rfloor}}.
\]
\label{thm:lower}
\end{theorem}

\noindent
\textbf{Proof:}
By Theorem~\ref{thm:cycles}, there exists a cycle on the radual graph
  of a monotone $n$-Venn of size $2{n \choose k}$,
  where $k = \lfloor n/2 \rfloor$.
Since this cycle alternates between dual vertices and Venn vertices,
  \[ M_n \ge {n \choose {\lfloor n/2 \rfloor}}. \]
\hfill $\Box$

\subsection{A Straightened Venn Diagram}

Suppose that $V$ is an $n$-Venn diagram with a vertex $v$ such that
  $deg(v) = 2n$.
Let $v$ have a vertex traversal such that it is possible to
  split it into two copies where each copy is adjacent to
  $n$ distinct curves; i.e., where the vertex traversal
  consists of two contiguous subsequences, each containing $n$
  curves.
Imagine pulling the two copies of $v$ apart, horizontally stretching
  the rest of the curves so one of the curves $C$ becomes a straight
  line segment.
Each of the curves and the intersections are stretched but do not
  change their original relationships.
The resulting diagram represents a Venn diagram with $n$ simple
  curve segments beginning and ending at the two copies of $v$.
The exterior region is now represented by the area above the curves
  and the interior region is represented by the region below
  the curves.
We call this diagram a \emph{straightened representation of $V$}.

\begin{definition}
We define an $n$-{\em Straightened} Venn Diagram, ($n$-SVD) as
  a straightened representation of an $n$-Venn
  diagram, $V_n$ with the following properties:
\begin {enumerate}
  \item The curve $C_n$ is a horizontal line segment, beginning and
    ending on the two copies of vertex $v_1$, named
    $v_1^{\textrm{\scriptsize{L}}}$
    and $v_1^{\textrm{\scriptsize{R}}}$.
  \item All vertices of $V_n$ lie on $C_n$
    and are numbered $v_1^{\textrm{\scriptsize{L}}}, v_2, \ldots ,
    v_m, v_1^{\textrm{\scriptsize{R}}}$.
  \item There are exactly $n$ vertices with degree $2n$, including
    $v_1$ and $v_2$.
  \item Any vertical line drawn through $C_n$ intersects each curve
    exactly once.
  \item All non-adjacent vertices on $C_n$ are the endpoints of  exactly $0$
    or $2$ edges.
\end {enumerate}
\label{def:SVD}
\end{definition}
Note that this diagram becomes a Venn diagram if we join the two copies
  of $v_1$ and make $C_n$ a circle.

\begin{lemma}
Any SVD represents a monotone Venn diagram.
\label{lem:mono}
\end{lemma}

\noindent
\textbf {Proof:}
By definition, the SVD represents a Venn diagram.
It follows from Property 4 that the vertical line can be seen as a path
  through the directed dual graph, starting in the upper region, and
  ending in the lower.
\hfill $\Box$

\begin{lemma}
In an $n$-SVD, the number of curves intersecting at a vertex
  has the same parity as $n$.
\label{lem:parity}
\end{lemma}

\noindent
\textbf {Proof} (by induction on $v_k$):

Let $h_k$ be the number of curves intersecting at a vertex $v_k$.
Note that $h_k = deg(v_k)/2$.
Also, since an SVD is monotone, $h_k$ is the number of edges from
  $v_i$ to $v_k$, taken over all $i$ for which $1 \le i < k \le n$.

\noindent
\textbf {Base Case:}
By property $3$ of Definition~\ref{def:SVD}, $h_1 = n$.

\noindent
\textbf {Inductive Step:}
Assume the statement is true for all $v_k$, where $k \ge 1$.

Let the number of edges from $v_k$ to $v_{k+1}$ be $c$.
Let the number of edges from $v_k$ to $v_l$, where $l > k+1$,
  be $d$.
Let the number of edges from $v_j$ to $v_{k+1}$, where
  $j < k$, be $g$.
Then $h_k = c + d$, and $h_{k+1} = c + g$.
By Property $5$ of Definition~\ref{def:SVD}, $d$ and $g$ are even.
Then by the induction hypothesis, $c$ must have the same parity as $n$.
Therefore, $h_{k+1}$ has the same parity as $n$.
\hfill $\Box$

\vspace{\baselineskip}
Before we can construct an $(n+1)$-SVD from an $n$-SVD, we need a method
  to reduce the number of vertices on a Venn diagram.
This method is defined in the next section.

\subsubsection{Vertex Compression}

We can {\em compress} $2$ adjacent vertices $v$ and $w$ on a Venn diagram
  if they share exactly one common curve $C$.
This is done by removing the edge $C(vw)$ and then mending
  the curve $C$ by merging $v$ and $w$.
The process reduces the number of vertices by one, while maintaining the
  Venn diagram properties.
All curves remain simple and closed and no regions have been
  created or destroyed.

We use this operation to prove the next theorem.
An illustration of the proof can be found in Figure~\ref{fig:construct},
  for the case $n=4$.

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{constructionBW.pstex_t} }
  { \input{construction.pstex_t} }
\end{center}
\caption{Constructing $V_5$ from $V_4$}
\label{fig:construct}
\end{figure}

\begin{theorem}
An $n$-SVD can be extended to an $(n+1)$-SVD.
\label{thm:extend}
\end{theorem}

\noindent
\textbf{Proof:}
Let $V_n$ be an $n$-SVD with $m$ vertices.
Divide the plane into $m$ sections $P_1, P_2, \ldots ,P_m$,
  each section delimited by two vertical lines through
  two consecutive vertices on $V_n$.

\noindent \textbf{Step 1 :}
We draw a new curve $C_{n+1}$ beginning at $v_1^{\textrm{\scriptsize{L}}}$,
  and ending on $v_1^{\textrm{\scriptsize{R}}}$.
In each $P_i$, we move up to the highest region that has not been previously
  visited, and sweep downwards as far as possible through all non-visited
  regions, crossing curves as necessary.
We exit each $P_i$ through the bordering vertex, and continue in this
  manner until we reach $v_1^{\textrm{\scriptsize{R}}}$.
Since $C_{n+1}$ passes through all $2^n$ regions, at the end of this
  step, we have a representation of a monotone Venn diagram which has
  been cut at $v_1$.

\noindent \textbf{Step 2:}
The curve $C_{n+1}$, while in $P_i$, intersects $0 \le r \le n$ distinct
  curves on its downward sweep before it exits through the right vertex.
For $r \ge 2$, we can apply the above compression operation $r-1$ times and
  create exactly one vertex from the previous $r$ vertices.
This operation, performed similarly in each section, reduces the number of
  newly created vertices to no more than $2m$.

\noindent \textbf{Step 3:}
Straighten $C_{n+1}$.

\vspace{\baselineskip}
\noindent The new diagram is an $(n+1)$-SVD because
\begin{enumerate}
  \item The curve $C_{n+1}$ is the straightened horizontal line segment,
    beginning and ending on the two copies of $v_1$.
  \item Since $C_{n+1}$ passes through all existing vertices, and creates
    the only new ones, all vertices lie on $C_{n+1}$, and are numbered
    $v_1^{\textrm{\scriptsize{L}}} = w_1^{\textrm{\scriptsize{L}}},
    w_2, \ldots , w_t, w_1^{\textrm{\scriptsize{R}}} =
    v_1^{\textrm{\scriptsize{R}}}$, where $t \le 2m$.
  \item $C_{n+1}$ crosses all existing curves in one downward sweep in the
    first section of $V_n$, between $v_1^{\textrm{\scriptsize{L}}}$ and
    $v_2$, and these new vertices are compressed to form one vertex
    of degree $2(n+1)$.
  After that, $C_{n+1}$ does not venture into the upper or lower regions
    again, and therefore we cannot produce another compression
    involving all the curves.
  The curve $C_{n+1}$ passes through all existing vertices on $V_n$, so any
    vertices that had degree $2n$ previously, will now have degree $2(n+1)$.
  The total number of vertices having degree $2(n+1)$ is $n+1$.
  \item Since $C_{n+1}$ is a straight line, it can be intersected by
    a vertical line exactly once.
  The curves of $V_n$ continue to move left to right in the new diagram.
  \item If vertices $u$ and $w$ are non-adjacent in $V_n$, then there are
    zero or two edges incident to both.
  If the number is two, then $C_{n+1}$ has already visited the regions
    above and below these edges, before passing through $u$.
  In either case, $C_{n+1}$ does not alter the number of edges incident to
    $u$ and $w$.

  If the vertices are adjacent in $V_n$, then prior to passing through $u$,
    curve $C_{n+1}$ has either visited the regions above and below the
    outermost edges, or it has not.
  If it has not, then $C_{n+1}$ crosses all the edges, and $u$ and
    $w$ share no edges in the new diagram.
  If it has, then $C_{n+1}$ does not cross the upper and lower edges,
    and $u$ and $v$, if they are no longer adjacent, are the endpoints
    of exactly two edges.
\end{enumerate}
\hfill $\Box$

% \subsubsection{A Specific Set of SVDs}

If we use the same construction described in the proof of
  Theorem~\ref{thm:extend}, for all values of $n$, we create
  a sequence $V_2, V_3, V_4, \ldots$ of SVDs that has very
  interesting properties.
When discussing SVDs from now on, we specifically refer to this set.

The construction of the first two diagrams is described below.
\begin{enumerate}
  \item For $n=1$, the curve $C_1$ is a horizontal line segment which divides
    the plane into an upper and lower region.
  \item For $n=2$, the curve $C_2$ starts at $C_1$'s leftmost point, moves up to the
    upper region, crosses $C_1$ into the lower region and stops
    at $C_2$'s rightmost point.
  No compression is necessary and $C_2$ becomes the new straight line segment.
\end{enumerate}
The next four diagrams created by our construction are shown in
  Figure \ref{fig:bases}.

\subsection{Properties of SVDs}

\subsubsection{Structural Properties}

Let $V_n$ be a straightened $n$-Venn diagram, constructed as described
  in the previous section.
Let $v_i$ be a vertex on $V_n$ that has degree $2n$.
And let $v_j$ be the next vertex to the right of $v_i$, which also
  has degree $2n$.
We will call the portion of $V_n$ which is contained between these
  $2$ vertices a {\em football}, $F^n_k$, where $k$ is an index number
  of the football, as we count from left to right.
By Definition~\ref{def:SVD}, $1 \le k \le n$.

Each football has a {\em boundary}, which consists of the edges
  that border the outer and inner region.
A boundary edge is sometimes referred to as the upper or lower
  boundary edge.

Note that due to the method of construction, $C_n$ splits $F^{n-1}_1$ into
  $F^n_1$ and $F^n_2$.
For $k>1$, $C_n$ does not cross a boundary in $F^{n-1}_1$.
These two facts mean that the modified $F^{n-1}_{k-1}$ in $V_{n-1}$
  is re-indexed as $F^n_k$ in $V_n$.

\begin{lemma}
The topological structure of $F^n_k$, where $1 \le k \le n$, is covered
  by one of the following statements:
\begin{enumerate}
  \item When $1 \le k \le 2$, it is a collection of $n$ labelled edges.
  \item When $3 \le k \le n-1$, it is a boundary containing
    $F^{n-2}_1 \cdots F^{n-2}_{k-1}$, as illustrated in
    Figure~\ref{fig:football}.
  \item When $k=n$ it is a boundary containing
    $F^{n-2}_1 \cdots F^{n-2}_{n-2}$.
\end{enumerate}
\label{lem:content}
\end{lemma}

\noindent
\textbf{Proof} (by induction on $n$):

See Figure~\ref{fig:bases} for the base cases
  of $n=2$ and $n=3$.

Assume the statement is true for $F^{n-1}_1$.
The curve $C_n$ passes through all curves in $F^{n-1}_1$, from the
  upper to lower region.
After compression and straightening $C_n$, we produce $F^n_1$ and
  $F^n_2$, divided by the only new vertex.
Thus statement $1$ is proven.

Assume the lemma is true for $F^{n-1}_{k-1}$ and
  consider $3 \le k \le n-1$:
When constructing $F^n_k$ from $F^{n-1}_{k-1}$, the curve $C_n$
  does not cross the boundary, since $k>2$.
For $k = 3$, the action of adding $C^n$ to $F^{n-1}_2$ creates
  a single vertex compressing $n-3$ labelled edges.
When $C^n$ is straightened, the structure within the newly indexed
  $F^n_3$'s boundary is identical to $F^{n-2}_1 F^{n-2}_2$.

\begin{landscape}
\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{basesBW.pstex_t} }
  { \input{bases.pstex_t} }
\end{center}
\caption{The First 6 Straightened Venn Diagrams}
\label{fig:bases}
\end{figure}
\end{landscape}

For $k > 3$, by the induction hypothesis, $F^{n-1}_{k-1}$'s boundary
  contains $F^{n-3}_1 \cdots F^{n-3}_{k-2}$.
For the special case of $k = n$, the boundary does not contain
  $F^{n-3}_{k-2}$, and for simplicity, this is assumed in
  all future statements concerning $F^n_k$.
When $C_n$ is added to create $F^n_k$ from $F^{n-1}_{k-1}$, its action inside
  the boundary follows the same pattern as $C_{n-2}$ does
  in $F^{n-3}_1 \cdots F^{n-3}_{k-2}$, when creating $V_{n-2}$
  from $V_{n-3}$.
The modified $F^{n-3}_1 \cdots F^{n-3}_{k-2}$ in $V_{n-3}$ becomes
  $F^{n-2}_1 \cdots F^{n-2}_{k-1}$, in $V_{n-2}$.
The modified $F^{n-1}_{k-1}$, re-indexed as $F^n_k$ in $V_n$, contains
  $F^{n-2}_1 \cdots F^{n-2}_{k-1}$.
Thus statements $2$ and $3$ are proven.

\hfill $\Box$

\begin{figure}
\begin{center}
\ifthenelse{\value{BlackWhite} = 1}
  { \input{footballBW.pstex_t} }
  { \input{football.pstex_t} }
\end{center}
\caption{The Topological Structure of $F^6_5$}
\label{fig:football}
\end{figure}

\subsubsection{Curve Properties}

Another property of these straightened Venn diagrams is that within each
  football, the {\em curve segment} of $C_i$ has a predictable placement.
It is clear from the construction that the curve segments in $F^n_1$
  are the edges ordered $C_n, \ldots ,C_1$ and the curve segments in
  $F^n_2$ are ordered $C_{n-1}, \ldots ,C_1, C_n$.

\begin{lemma}
For $2 \le k \le n$, the curve segment of $C_j$ in $F^n_k$ is described by one
  of the following statements:
\begin{enumerate}
  \item When $1 \le j < n-k+1$, the segment is the same as its placement in
     $F^{n-2}_1 \cdots F^{n-2}_{k-1}$.
  \item When $j = n-k+1$, the segment is the upper boundary.
  \item When $j = n-k+2$, the segment is the lower boundary.
  \item When $n-k+2 < j \le n$, the segment replaces the segment of
    $C_{j-2}$ in $F^{n-2}_1 \cdots F^{n-2}_{k-1}$.
\end{enumerate}
\label{lem:curves}
\end{lemma}

\noindent
\textbf{Proof:}
Note that for simplicity, when $k=n$, we assume that references to
  $F^{n-2}_1 \cdots F^{n-2}_{k-1}$ do not include $F^{n-2}_{k-1}$.

When $j=n$, $C_j$ is the straight line segment.
It is the upper boundary of $F^n_1$, the lower boundary of $F^n_2$, and
  clearly replaces $C_{n-2}$ in all of $F^n_3 \cdots F^n_n$.

For $k=2$, the curves are $C_{n-1}, \ldots ,C_1, C_n$,
  from upper to lower boundary, so statements $1$, $2$ and $3$ are proven,
  and $4$ is not applicable.

For $k>2$ and $j<n$, we use induction on $n$.  See Figure~\ref{fig:bases}
  for the base cases of $n=2$ and $n=3$.

\noindent \textbf{Inductive Step:}  Assume the statement is true for
  any $C_j$ in $F^{n-1}_k$.

Since $n-k+1 = n-1-(k-1)+1$, and $n-k+2 = n-1-(k-1)+2$,
  we use the induction hypothesis to claim that boundaries of
  $F^{n-1}_{k-1}$ remain the same boundaries when $F^n_k$ is
  created.
Thus statements $2$ and $3$ are true for all $n$.

For non-boundary values of $j$, we invoke the induction hypothesis
  to claim that $C_j$ in $F^{n-1}_{k-1}$ is either the same as its
  placement, or is replacing $C_{j-2}$, in $F^{n-3}_1 \cdots
  F^{n-3}_{k-2}$.
$C_n$ acts on $F^{n-1}_{k-1}$ in the same manner as $C_{n-2}$ acts
  on $F^{n-3}_1 \cdots F^{n-3}_{k-2}$, creating $F^n_k$ or
  $F^{n-2}_1 \cdots F^{n-2}_{k-1}$ respectively.
So $C_j$ in $F^n_k$ is either still the same as its placement,
  or is still replacing $C_{j-2}$, in $F^{n-2}_1 \cdots F^{n-2}_{k-1}$.
Thus statements $1$ and $4$ are true for all $n$.
\hfill $\Box$

\subsection{Counting the Vertices}

We have determined in the proof of Theorem~\ref{thm:extend}, that the
  number of vertices of $V_n$ is no more than twice the number of vertices
  of $V_{n-1}$.
In order to precisely determine the number of vertices,
  we need to subtract the number of times that $C_n$ passes
  through $2$ existing vertices in $V_{n-1}$, without crossing an edge.

% \subsubsection{Singleton Crossings}

For $n>2$, we say $V_n$ has a {\em singleton crossing},
  whenever it has a vertex of degree $4$.
During the construction of $V_{n+1}$, as $C_{n+1}$ exits this vertex,
  entering section $P_i$, it confines itself within the $2$ curves and
  does not create a new vertex before exiting $P_i$.
See the square vertices of Figure~\ref{fig:construct}(a).

\begin{lemma}
If a singleton crossing occurs on $V_n$, then $n$ is even.
\label{lem:single}
\end{lemma}

\noindent
\textbf{Proof:}
A singleton crossing means that $2$ curves cross at one vertex.
By Lemma~\ref{lem:parity}, $n$ must be even.
\hfill $\Box$

\vspace{\baselineskip}
Let $S(n,k)$ be the number of singleton crossings within the football $F^n_k$.
For clarity, we define $S(2,1) = 0$, and $S(2,2) = 1$.
We define $S(n)$ to be the total number of singleton crossings on
  an $n$-SVD.

\begin{lemma}
The number $S(n,k)$ is positive if and only if
  $n$ is even and $n/2 < k \le n$.
\label{lem:positive}
\end{lemma}

\noindent
\textbf{Proof} (by induction on $n$):

Obviously $k \le n$, so we deal specifically with $n/2 < k$.

\noindent\textbf{Base Case:}
For $n = 2$, $S(2,2) = 1$, and $S(2,1) = 0$.

\noindent \textbf{Inductive Step:}
Suppose it is true for $n - 2$ and consider $F^{n}_k$.

Suppose $S(n,k) > 0$:
We know that $n$ is even (by Lemma~\ref{lem:single}).
Let $F^{n-2}_i$ be a football contained within the boundary of
  $F^n_k$, such that $S(n-2,i) > 0$.
Then by Lemma~\ref{lem:content} $1 \le i \le k-1$ and
  by the induction hypothesis
\[ i > \frac{n-2}{2} \]
Therefore $n/2-1 < i. \le k-1$, which implies that $n/2 < k$.

Suppose $n$ is even and $n/2 < k \le n$.
By Lemma~\ref{lem:content}, $F^n_k$ contains
  $F^{n-2}_1 \cdots F^{n-2}_{k-1}$ within its boundary.
Since $k-1 > n/2-1$, by the induction hypothesis
    $F^{n-2}_{k-1}$ must have a singleton crossing.
Therefore, $S(n,k) > 0$.
\hfill $\Box$

\vspace{\baselineskip}
We now present three little corollaries concerning $S(n,k)$:

\begin{corollary}
For all $n \ge 2$, we have $S(n,n) = S(n,n-1)$.
\end{corollary}

\noindent
\textbf{Proof:}
By Lemma~\ref{lem:content}, we know that the unlabeled $F^n_{n-1}$ is
  identical to the unlabeled $F^n_n$.
\hfill $\Box$

\begin{corollary}
If $n$ is even and $n \ge 2$, then $S(n,n/2+1) = 1$.
\end{corollary}

\noindent
\textbf{Proof} (by induction on $n$):

\noindent \textbf{Base Case:}\[ S(2,2) = 1 \]

\noindent \textbf{Inductive Step:}
Suppose it is true for $S(n-2,n/2)$.
Then
\begin{eqnarray*}
  S(n,n/2+1) &=& \sum_{i=1}^{n/2} S(n-2,i)
                 \;\;\;\;\;\; \textrm{ (by Lemma~\ref{lem:content})}\\
             &=& \sum_{i=1}^{n/2-1} S(n-2,i) + S(n-2,n/2) \\
             &=& 0 + 1 = 1
                 \;\;\; \textrm{ (by Lemma~\ref{lem:positive} and
                  the induction hypothesis).}
\end{eqnarray*}
\hfill $\Box$

\begin{corollary}
For all $1 \le k \le n$,
\[ S(n,k) = S(n,k-1) + S(n-2,k-1) \].
\label{cor:third}
\end{corollary}

\noindent
\textbf{Proof:}
\begin{eqnarray*}
  S(n,k) &=& \sum_{i=1}^{k-1} S(n-2,i)
            \;\;\;\;\;\; \textrm{ (by Lemma~\ref{lem:content})}\\
         &=& \sum_{i=1}^{k-2} S(n-2,i) + S(n-2,k-1) \\
         &=& S(n,k-1) + S(n-2,k-1).
\end{eqnarray*}
\hfill $\Box$

\vspace{\baselineskip}
Define $T(n,k)$ to be the number of well-formed parentheses strings
  of length $2n$, which begin with exactly $k$ left parentheses.
The following recurrence relation for $T(n,k)$ is proven in
  Hu and Ruskey~\cite{HuRusk}.
\[
T(n,k) = \left\{ \begin{array}{ll}
   T(n,2)                                    & \mbox{if $k=1$} \\
   T(n,k+1)+T(n-1,k-1)                       & \mbox{if $1 < k < n$} \\
   1                                         & \mbox{if $k=n$.}
   \end{array}
   \right.
\]

We use $T(n,k)$ to demonstrate a relationship between $S(n)$ and
  $C(n)$, the $n$th Catalan number.
The Catalan numbers count the total number of well-formed parentheses strings
  of length $2n$.
Two equations for $C(n)$ are given below.
\begin{eqnarray*}
  C(n) &=& \frac{1}{n+1} {2n \choose n} \\
       &=& \sum_{i=1}^n T(n,i).
\end{eqnarray*}


\begin{lemma}
For an even integer $n>1$,
\[ S(n,k) = T(n/2,n-k+1) \textrm{.} \]
\label{lem:Tnk}
\end{lemma}

\noindent
\textbf{Proof} (by induction on k):

\noindent \textbf{Base Case:}
\[ S(n,n/2+1) = 1 = T(n/2,n/2) \]
\noindent \textbf{Inductive Step:}
Assume the statement is true for all values less than $k$:
\begin{eqnarray*}
  S(n,k) &=& S(n,k-1) + S(n-2,k-1) \hfill
           \;\;\;\;\;\; \textrm{ (by Corollary~\ref{cor:third})} \\
         &=& T(n/2,n-k+2) + T(n/2-1,n-k) \\
         &=& T(n/2,n-k+1).
\end{eqnarray*}
And
\[
  S(n,n) = S(n,n-1) = T(n/2,2) = T(n/2,1).
\]
\hfill $\Box$

\begin{corollary}
For $n = 2m$, the number of singleton crossings $S(n)$ on $V_n$,
  is $C(m)$.
\end{corollary}

\noindent
\textbf{Proof:}
\begin{eqnarray*}
  C(m) &=& \sum_{i=1}^m T(m,i) \\
      &=& \sum_{j=m+1}^n S(n,j) \hfill
         \;\;\;\;\;\; \textrm{ (by Lemma~\ref{lem:Tnk})} \\
      &=& S(n).
\end{eqnarray*}
\hfill $\Box$

\subsubsection{Subtracting the Singleton Crossing from $2M_n$}
We know from the proof of Theorem~\ref{thm:extend} and the previous section,
  that if $Vn$ has $M_n$ vertices, then $V_{n+1}$ has $2M_n-S(n)$
  vertices.

\begin{theorem}
\[ M_n = {n \choose {\lfloor n/2} \rfloor} \textrm{.}
\]
\end{theorem}

\noindent
\textbf{Proof:}
Theorem~\ref{thm:lower} showed that $M_n \ge {n \choose {n/2}}$.
We proceed by induction on $n$.

\noindent \textbf{Base Cases:}
Observe that $M_2 = 2$ and $M_3 = 3$, by Figure~\ref{fig:bases}.

\noindent\textbf{Inductive Step:}
Let $n = 2m$, and assume that for all $k < n$,
\[ M_k = {k \choose {\lfloor k/2 \rfloor}} \textrm{.}
\]

Then for $n$, which is even,
\begin{eqnarray*}
  M_n &\le& 2M_{n-1} - S(n-1,k) \;\; = \;\; 2M_{n-1} \\
      &=& 2 {{2m-1} \choose {m-1}} \\
      &=& \frac{2(2m-1)!}{(m-1)!m!} \\
      &=& \frac{2m(2m-1)!}{m(m-1)!m!} \\
      &=& \frac{2m!}{m!m!} \\
      &=& {{2m} \choose {m}} \\
      &=& {n \choose {\lfloor n/2 \rfloor}}.
\end{eqnarray*}
And for $n+1$, which is odd,
\begin{eqnarray*}
  M_{n+1} &\le& 2M_n - S(n) = 2M_n - C(m) \\
          &=& 2{{2m} \choose m} - \frac{1}{m+1} {{2m} \choose m} \\
          &=& \frac{2(m+1)-1}{m+1} {{2m} \choose m} \\
          &=& \frac{(2m+1)(2m)!}{(m+1)m!m!} \\
          &=& \frac{(2m+1)!}{(m+1)!m!} \\
          &=& {{2m+1} \choose m} \\
          &=& {n \choose {\lfloor n/2 \rfloor}}.
\end{eqnarray*}
\hfill $\Box$

\section{Acknowledgements}

We wish to express our thanks to Branko Gr\"{u}nbaum and Peter Hamburger
  for their helpful comments and discussion regarding this paper.
Research supported in part by grants from the Natural Science and
  Engineering Research Council of Canada.

{\small
\begin{thebibliography}{99}
\bibitem{BuRuGr}
B. Bultena, B. Gr\"{u}nbaum, and F. Ruskey,
  ``Convex Drawings of Intersecting Families of Simple
  Closed Curves,'' submitted manuscript, 1998.
\bibitem{CHP1} K.B. Chilakamarri, P. Hamburger and R.E. Pippert, ``Hamilton
  Cycles in Planar Graphs and Venn Diagrams,''
  \emph{Journal of Combinatorial Theory}, B 67 (1996) 296-303.
\bibitem{CHP2} K.B. Chilakamarri, P. Hamburger and R.E. Pippert, ``Venn
  Diagrams and Planar Graphs,'' \emph{Geometriae Dedicata}, 62 (1996) 73-91.
\bibitem{Edwards}
  A.W.F. Edwards, ``Seven-set Venn diagrams with rotational and polar
  symmetry,'' \emph{Combinatorics, Probability, and Computing},
  7 (1998) 149-152.
\bibitem{Edwards1}
  A.W.F. Edwards, ``Venn diagrams for many sets,''
  \emph{Bulletin of the International Statistical Institute}, 47th Session,
  Paris (1989)  Contributed papers, Book 1, 311-312.
\bibitem{Edwards2}
  A.W.F. Edwards, ``Venn diagrams for many sets,''
  \emph{New Scientist}, 7 (January 1989) 51-56.
\bibitem{Grun}
  B. Gr\"{u}nbaum, ``Venn diagrams and Independent Families of Sets.''
  \emph{Mathematics Magazine}, 48 (Jan-Feb 1975) 12-23.
\bibitem{Ha98} P. Hamburger, ``A Graph-theoretic approach to Geometry,''
  manuscript, 1998.
\bibitem{HuRusk} T.C. Hu and F. Ruskey, ``Generating Binary Trees
  Lexicographically,'' \emph{SIAM J. Computing}, 6 (1977) 745-758.
\bibitem{Ruskey} F. Ruskey, ``A Survey of Venn Diagrams,''
  \emph{Electronic Journal of Combinatorics}, 4 (1997) DS\#5.
\end{thebibliography}
}

\end{document}