definitions.tex

%!TEX root = main.tex
\section{%Standard Definitions}%
  Preliminaries}
\seclabel{definitions}

We recall some % begin with fairly
standard definitions. % and then move on to problem-specific definitions and results.

%\subsection{Standard Definitions}

% For a function $f\colon\R\to\R$, we use $\lim_{x\downarrow t} f(x)$ and
% $\lim_{x\uparrow t} f(x)$ to denote the one-sided limits of $f(x)$
% as $x$ approaches $t$ from above and below, respectively.  
%
A \emph{curve} $C$ is a continuous function from $[0,1]$
to $\mathbb{R}^2$.  The points $C(0)$ and $C(1)$ are the \emph{endpoints} of $C$.  A curve $C$ is \emph{simple} if $C(s)\neq C(t)$
for $s\ne t$ % any $0\le s<t\le 1$
except possibly for $s=0$ and $t=1$; it is \emph{closed} if $C(0)=C(1)$.  A \emph{Jordan
	curve} $C\colon [0,1]\to\R^2$ is a simple closed curve.  
%Starting in the current paragraph, 
We will often not distinguish between a curve $C$ and its
image $\{C(t):0\le t\le 1\}$. % When this happens, we may qualify the
% curve as
The \emph{open curve} is the set $\{C(t):0< t< 1\}$.
%
A point $x\in\R^2$ lies \emph{on} $C$ if $x\in C$.  % !! NITPICKUNG
%
For any Jordan curve $C$, $\R^2\setminus C$ has two connected
components: One of these, $C^-$, is finite (the {\em interior} of $C$) and the other, $C^+$, is
infinite (the {\em exterior} of $C$).  
%We say that a Jordan curve is \emph{well-oriented} if walking
%along $C$ from $C(0)$ to $C(1)$ results in a counterclockwise traversal
%of the boundary of $C^-$, so that $C^-$ is locally to the left of $C$
%and $C^+$ is locally to the right of $C$. NOT USED?
%
The points on a simple curve $C$ are associated with a partial order $\prec_C$ such that $C(a)\prec_C C(b)$ if and only if $a<b$.  

%For any $0\le a\le b\le 1$, the \emph{subcurve}
%of $C$ between $a$ and $b$ is the curve $C'(t)=C(a+t(b-a))$.  When talking about the subcurve of $C$ between points $x,y\in C$ where $x\prec_C y$, we mean the subcurve of $C$ between the unique $a< b$ with $x=C(a)$ and $y=C(b)$. NOT USED?

All graphs $G$ considered in this paper are finite, simple, and
undirected.   We use $V(G)$ and $E(G)$ to denote the vertex set and edge
set of $G$, respectively.
% For any two vertices $x,y\in V(G)$,
We use $xy$
to denote the edge between the vertices % of $G$ incident to
$x$ and $y$. % We denote by $d_v$ the degree of a vertex $v$ in a graph. 

A \emph{drawing} %$\Gamma=(G,\varphi,\rho)$
of a graph $G$ consists of $G$ together with
 a one-to-one mapping $\varphi\colon V(G)\to\R^2$ and a mapping $\rho$ from
$E(G)$ to curves in $\R^2$ such that, for each $xy\in E(G)$, $\rho(xy)$
has endpoints $\varphi(x)$ and $\varphi(y)$.
%When speaking of a drawing,
%Most of the time, we will just speak of a drawing $G$,
We will not distinguish between a drawing $G$ and the underlying graph
$G$, and we will never
%without
explicitly refer to $\varphi$ and $\rho$.
In particular, we will sometimes have a drawing $G$ and we will speak about constructing
a different drawing of $G$, without danger of confusion.
%, it is clear what is meant.
%In these cases, we identify vertices of $G$ with their
%points and edges of $G$ with their curves.
%
In a \emph{straight-line drawing}, each edge is a straight-line
segment. In a \emph{plane drawing}, each edge is a simple curve, and no
two edges intersect, except possibly at common endpoints. A
\emph{F\'ary drawing} is a plane straight-line drawing.
% For a given F\'ary drawing $G$, we often address the problem of constructing a different F\'ary drawing of $G$, satisfying certain properties; by this we mean that we will construct a F\'ary drawing of the plane graph of which $G$ is a F\'ary drawing.

By default, an edge curve includes
its endpoints, otherwise we refer to it as an \emph{open} edge.
%
The \emph{faces} of a plane drawing $G$ are the maximal connected
subsets of $\R^2\setminus\bigcup_{xy\in E(G)} xy$.  One of
these faces, the \emph{outer} face, is unbounded; the other faces are called \emph{inner} or \emph{bounded} faces. A {\em boundary vertex} is incident to the outer face, other vertices are called \emph{interior} vertices.
%A \emph{chord} is an edge of $G$ with two endpoints on the outer face but whose
%interior is not on the outer face.  
%When discussing plane drawings, we use the convention of listing
%the vertices of a face as they appear when traversing the face in
%counterclockwise order. NOT REALLY
 If
 $C$ is a
cycle %separating triangle
 in a plane drawing, then
 % for any separating cycle $C$,
 there is a 
%well-oriented 
Jordan curve whose image
is the union of edges in $C$.  In this case, the interior and exterior of
$C$ refer to the interior and exterior of the corresponding Jordan curve.
% IS THIS EVER NEEDED?

A \emph{triangulation} (a \emph{quadrangulation}) is a plane drawing,
not necessarily with straight edges,
in which each face is bounded by a 3-cycle (respectively, a 4-cycle). 
%Every quadrangulation has
%$n\ge 4$ vertices and Euler's formula implies that it has $2n-4$ edges. NOT USED?

%A \emph{separating cycle} of a graph $G$ is a sequence of vertices
%that form a cycle and whose removal disconnects $G$.
A \emph{separating triangle} of a graph $G$ is
a cycle of length 3
 whose removal disconnects $G$.

The \emph{contraction} of an edge $xy$ in a graph $G$ identifies $x$
and $y$
into a new vertex~$v$.
Formally, we obtain a new graph $G'$ with
$V(G')=V(G)\cup\{v\}\setminus\{x,y\}$ and $E(G')=E(G)\setminus\{ab\in
E(G): \{a,b\}\cap\{x,y\}\neq\emptyset\}\cup\{va: xa\in E(G)\text{ or }
ya\in E(G)\}$.  
%In this case, we say that we \emph{contract} $xy$ in $G$ to obtain the graph $G'$.  EASY TO FIGURE
If $G$ is a triangulation and we
contract the edge $xy\in E(G)$, then the resulting graph $G'$ is also
a triangulation provided that $xy$ is not part of a separating
triangle. %More specifically,
Any plane drawing of $G$ leads naturally
to a plane drawing of $G'$.

\subsection{Characterization of Collinear Sets}


% A %well-oriented 
% Jordan curve $C$ is \emph{admissible} for a drawing $G$ if $C(0)=C(1)$ is in the outer face
% of $G$ and the intersection between $C$ and each edge $e$ of $G$ is
% either empty, a single point, or the entire edge $e$.  

%We say that $C$
%is \emph{proper} for $G$ if it is admissible and it does not contain any
%vertex of $G$; i.e., $C$ is proper if its intersection with any edge $e$
%of $G$ is either empty, or in the interior of $e$.

%We say that a Jordan curve $C:[0,1]\to\R^2$ is \emph{nice} for an embedded
%graph $G$ if $C$ intersects each edge of $G$ in at most one connected
%component and the endpoint $C(0)=C(1)$ of $C$ is in the interior of the
%outer face of $G$.  We say that $C$ is \emph{clean} (for $G$) if its
%intersection with each edge of $G$ is either empty or a single point.
%We say that $C$ is \emph{tidy} (for $G$) if it does not contain any
%vertex of $G$.

We will make use of the following restatement of \thmref{collinear-set}
which follows from the proof in \cite{dalozzo.dujmovic.ea:drawing}:
\begin{thm}\thmlabel{dujmovic-frati}
	For any planar graph $G$, the following two statements are equivalent:
	\begin{compactenum}
   \item There is a plane drawing %$\Gamma_1$
          of $G$ and an
		proper good curve $C\colon [0,1]\to\R^2$ such that the sequence of edges
and vertices intersected by $C$ is $r_1,\ldots,r_k$.
\item There is a \Fary\ drawing % $\Gamma_2$
  of $G$ in which the sequence of edges and vertices intersected by
  $Y$ is $r_1,\ldots,r_k$.
	\end{compactenum}
\end{thm}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "freecoll"
%%% End: