% LaTeX2e, amsart                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{amsart}

%\usepackage[cp1251]{inputenc}
%%\usepackage[russian]{babel}
%%%%%

\language0

\usepackage{amsmath,amssymb,amscd,eepic,color}
%\usepackage[all]{xy}

%%%%%%%%
%
% .eps  -обавлен пакет    epsf:
%
\usepackage{amsmath,amssymb,amscd,eepic,color,epsf}
%\usepackage[all]{xy}

%%%%%%%%
%
%іі1: я поменял размерv
%
\textwidth 15.5cm\hoffset=-1cm \textheight 24cm\voffset=-2cm
\headheight 0.5cm \evensidemargin1.25cm \oddsidemargin 1.25cm


\newtheorem{thm}{Tеорема}[section]
\newtheorem{thmnn}{Theorem\!\!}
\renewcommand{\thethmnn}{}
\newtheorem{prop}[thm]{іредложение}
\newtheorem{fig}[thm]{іисунок}
\newtheorem{Ex}[thm]{іример}

\newtheorem{lemma}[thm]{Tемма}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ques}[thm]{Question}
\theoremstyle{definition}
\newtheorem{rem}[thm]{іамечание}
\newtheorem{dfn}[thm]{+пределение}
\newtheorem{prpnn}{Proposition\!\!}

\newtheorem{dfnnn}{Definition\!\!}
\renewcommand{\thedfnnn}{}
\newcommand{ \PP } {\mathcal P}
\newcommand{ \MM } {\mathcal M}
\newcommand{ \RR } {\Bbb R}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\CC}  {\mathcal C}
\newcommand{ \PC } {\mathcal P}


%%%%%%%%
%
%іі2: следуіая абракадабра правильно форматирует подрисуночнvе подписи
%
\makeatletter
\long\def\@makecaption#1#2{%
  \vskip 10\p@
  \setbox\@tempboxa\hbox{#1. #2}% іаменили двоеточие на точку...
  \ifdim \wd\@tempboxa >\hsize
      \unhbox\@tempboxa\par
    \else
      \centerline{\box\@tempboxa}\fi}
\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname
  the#1\endcsname.}{\ignorespaces #2}}\begingroup
    \@parboxrestore
    \small%\normalsize
    \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
  \endgroup}
\makeatother
%%%%%%%%%

\title[Pointed graphs]
{Pointed graphs in the sphere and in the plane}
\author{Gaiane Panina}
%\address{}
\begin{document}
\maketitle                       
                                 
Presented by K. Kokhas, K. Kuyumzhiyan and G. Panina
\bigskip

\setcounter{section}{1}

As it was recently discovered, sometimes it  makes sense to consider
objects that are \emph{as non-convex as possible}.
For instance, to embed planar graphs in the plane  such that the tiles
do not look like convex polygons.

This helps to solve a series of problems which seemed to
be independent: A.\,D.\,Alexan\-drov's problem on uniqueness of convex 
surfaces, carpenter's rule problem,
some algorithmic problems on graphs embeddings...



Many problems are still to be solved. For instance, the problem N~17. 
Any progress in this direction would be of a
great interest.


Here is the most popular problem.

\subsection*{Carpenter's rule problem}

It was formulated in  1970
 by the leading authority in the rigidity theory R.
Connelly.

\emph{A carpenter's rule} is a non-crossing broken line in the
plane with a finite number of edges. It should be considered as a
so-called \emph{linkage  or a bar-and-join mechanism}, i.e., a
collection of rigid bars (line segments) that are hinged together
at the endpoints (vertices)  so that they can rotate with respect
to one another.

An \emph{isotopy} of a carpenter's rule is its continuous movement
in the plane which avoids self-intersections and preserves the
edges lengths.

\textsl{Is each carpenter's rule straightable in the plane (the
self-intersections should be avoided during the straightening)?}
(See Fig.~\ref{ris1.1})

\bigskip

\setlength{\unitlength}{1mm}

\begin{figure}
\begin{picture}(90,40)
\path(6,20)(18,31)(12,22)(27,23)(19,28)(38,20)(17,34)(10,30)%
(18,40)(44,20)(32,12)(32,21)(26,11)(20,18)(21,10)(33,10)(13,6)%
(12,20)(25,19)(29,23)
\put(50,20){$\longrightarrow$}
\path(57,40)(63,35)(71,30)(80,22)(90,16)(97,8)
%
%Tеперь ставим точечки на первvй путь
%
\put(18,31){\circle*1}\put(12,22){\circle*1}
\put(27,23){\circle*1}\put(19,28){\circle*1}
\put(38,20){\circle*1}\put(17,34){\circle*1}
\put(10,30){\circle*1}\put(18,40){\circle*1}
\put(44,20){\circle*1}\put(32,12){\circle*1}
\put(32,21){\circle*1}\put(26,11){\circle*1}
\put(20,18){\circle*1}\put(21,10){\circle*1}
\put(33,10){\circle*1}\put(13,6){\circle*1}
\put(12,20){\circle*1}\put(25,19){\circle*1}
%
%L на второй
%
\put(63,35){\circle*1}\put(71,30){\circle*1}
\put(80,22){\circle*1}\put(90,16){\circle*1}
\end{picture}
\caption{Straightening of a carpenter's rule} \label{ris1.1}
\end{figure}


Although the carpenter's rule problem looks like an olympiad one, it
has no elementary solution (the problem has been open for 30 years).

\pagebreak[4]



\begin{enumerate}
 \item Carpenter's rule problem in the
3-dimensional space.

 Is each non-crossing  broken
line  straightable in $\mathbb{R}^3$?

(Mostly probably you will find a solution, but a detailed proof
would need some advanced knowledge.)

\end{enumerate}



\subsection*{Polygons in the plane and in the sphere}

\emph{A great semicircle} in the sphere is the intersection of the
sphere with a plane passing through its center.

 A polygon is
a non-crossing closed broken line  (its edges are line segments in
the plane or the segments of great circles in the sphere) taken
together with a bounded part of the plane (or the sphere) bounded
by the broken line.

A polygon can be  non-convex. Some of its angles can be greater
than $\pi$. Such angles are called non-convex. The angles smaller
than $\pi$ are called convex.


\begin{enumerate}
\setcounter{enumi}{1}

\item Does there exist a polygon in the plane with exactly two
convex angles?


\item  (A simple but a very important problem. To be used in the
sequel.) Draw a  4-gon in the sphere with exactly two convex
angles.


\end{enumerate}

\subsection*{Pointed graphs}

A graph in the plane or in the sphere is called  \emph{pointed} if

\begin{itemize}
\item   all its edges  are line segments (for a graph in the
plane) and segments of great circles (for a graph in the sphere);



\item  it is non-crossing (its edges have no intersections);

\item   (pointed property) every vertex is incident to an angle
greater than $\pi$   ( Fig. ~\ref{ris1.0}.);

\item its vertices are in generic position.
\end{itemize}


\begin{figure}[b]

%
\hfil
\begin{minipage}[b]{.57\linewidth}
\begin{picture}(50,34)
%\color{red}
\path(2,5)(12,20)(30,0)(35,5)(36,9) \path(32,15)(50,7)
\path(30,20)(19,22)
%\color{blue}
\path(7,0)(12,20) \path(30,0)(30,20)(15,30)
\path(35,5)(32,15)(39,32)
%\color{black}
\put(12,20){\circle*1}\put(30,0){\circle*1}\put(35, 5){\circle*1}
\put(30,20){\circle*1}\put(32,15){\circle*1}
\end{picture}
\caption{Part of a pointed graph}
%$$\special{em:graph turgor2.bmp }$$
\label{ris1.0}
\end{minipage}
\end{figure}


A graph is called \emph{trivalent} if each its vertex has exactly
three adjacent edges.


\begin{enumerate}
\setcounter{enumi}{3}

\item Draw a pointed trivalent graph in the plane.



\item
 Does there exist a pointed graph in the sphere of radius  1 such that the area
of each tile is smaller than 1/10 and all its edges are shorter
than 1/10?
\end{enumerate}



\subsection*{Maximal pointed graphs}


A graph in the plane or in the sphere is called \emph{maximal
pointed} if it is impossible to add a new edge (without adding new
vertices) preserving the pointed property.

\begin{enumerate}
\setcounter{enumi}{5}

\item Draw a maximal pointed graph with 12 vertices in the plane.
    The vertices must not lie in convex position (i.e. they shouldn't serve as vertices of some
    convex polygon).

\item
    Prove the following two properties of a maximal pointed graph in the plane.

    1. There is a closed broken line consisting of some edges of the graph
     and bounding a convex polygon  $M$. All vertices of the graph lie in $M$.

    2. Each of the bounded tiles  has exactly 3 convex angles.

\end{enumerate}

\subsection*{Euler formula}

For a connected graph in the plane or in the sphere, we have
$$
V-E+F  = 2\,.
$$
Here  $V$ is the number of vertices,  $E$ is the number of edges,
$F$ is the number of tiles (for a graph in the plane, the unbounded tile
is also taken into account).

\bigskip

\begin{enumerate}
\setcounter{enumi}{7}


\item Let $ \Gamma$ be a maximal pointed graph in the plane.
Prove that
$$
E=2V-3\,.
$$


\item   
Draw an example of a  pointedgraph in the sphere such that

a) $E=2V - 2$.


b) $E=2V+2007$.


\item

a)  Can the graph 1   (Fig.~\ref{ris1.4}) be redrawn in the plane as a pointed 
graph? ("To redraw" means to construct another graph with another vertices (and
possibly with another edge
 lengthes), but  preserving the vertices-edges correspondence.

b)  Can the graph 1   (Fig.~\ref{ris1.4}) be redrawn in the plane
as a pointed graph  such that the unbounded tile is a complement
of a triangle?

c) Can the graph 2    (Fig.~\ref{ris1.4}) be redrawn in the plane
as a pointed graph?


\begin{figure}
%$$\special{em:graph turgor3.bmp }$$
\begin{picture}(110,50)
\path(45,20)(35,40)(45,40)(25,0)(45,0)(40,10)(30,10)(35,0)(45,20)(15,20)
\path(20,30)(10,10)(20,10)(35,40)
\path(20,10)(10,30)(15,40)(25,20)
\path(10,30)(40,30)
\path(30,30)(40,10)
\multiput(0,0)(-5,10){4}{\multiput(25,0)(10,0){3}{\circle*1}}
\multiput(45,20)(-5,10){3}{\circle*1}
\put(10,10){\circle*1}
\put(15,40){\circle*1}
\put(45,40){\circle*1}
\put(10,0){$1)$}
%
%Tеперь второй граф
%
\path(70,0)(90,10)(90,0)(70,10)(90,30)(100,20)(100,10)(70,10)(80,15)
\path(70,0)(70,20)(110,20)(90,10)(80,20)(80,15)(90,10)
\put(100,0){$2)$}
\put(70,0){\circle*1}\put(90,10){\circle*1}\put(90,0){\circle*1}
\put(70,10){\circle*1}\put(90,30){\circle*1}\put(100,20){\circle*1}
\put(100,10){\circle*1}\put(70,20){\circle*1}\put(80,15){\circle*1}
\put(110,20){\circle*1}\put(80,20){\circle*1}\put(80,5){\circle*1}
\put(100,15){\circle*1}
%\path(70,0)(85,0)(90,10)(90,40)(70,30)(70,0)(75,20)(80,30)(90,40)(85,0)(85,20)(75,0)
%\path(80,10)(75,20)(70,30)(80,30)(85,20)
%\put(95,0){$2)$}
%\put(70,0){\circle*1}\put(75,0){\circle*1}\put(85,0){\circle*1}
%\put(80,10){\circle*1}\put(75,20){\circle*1}\put(90,10){\circle*1}
%\put(85,20){\circle*1}
%\put(70,30){\circle*1}\put(80,30){\circle*1}\put(90,40){\circle*1}
\end{picture}
\caption{}
\label{ris1.4}
\end{figure}
%$$\special{em:graph turgor5.bmp }$$
\end{enumerate}


\section*{Problems presented after semifinal}

\subsection*{Trivalent pointed graphs}


A pointed trivalent graph \emph{admits a proper coloring} if each
its edge can be colored either red or blue such that at each of its
vertices the graph looks like as is depicted in Fig. 2 (two side
edges are of the same color, whereas the middle edge is of the
other color).

 \setlength{\unitlength}{1mm}
\begin{figure}[b]
\begin{minipage}[b]{.4\linewidth}
\begin{picture}(45,30)
%$$\special{em:graph turgor1.bmp }$$
\color{red} \path(0,3)(15,20)(10,0) \path(37,20)(20,0)
\color{blue} \path(7,2)(15,20) \path(29,20)(20,0)(42,10)
\color{black} \put(15,20){\circle*1}\put(20,0){\circle*1}
\end{picture}
\caption{Proper coloring} \label{ris1.2}
\end{minipage}
%
\hfil
\begin{minipage}[b]{.57\linewidth}
\begin{picture}(50,34)
\color{red} \path(2,5)(12,20)(30,0)(35,5)(36,9) \path(32,15)(50,7)
\path(30,20)(19,22) \color{blue} \path(7,0)(12,20)
\path(30,0)(30,20)(15,30) \path(35,5)(32,15)(39,32) \color{black}
\put(12,20){\circle*1}\put(30,0){\circle*1}\put(35, 5){\circle*1}
\put(30,20){\circle*1}\put(32,15){\circle*1}
\end{picture}
\caption{Part of a properly colored graph}
%$$\special{em:graph turgor2.bmp }$$
\label{ris1.3}
\end{minipage}
\end{figure}


\begin{enumerate}
\setcounter{enumi}{10}


\item Does there exist a properly colored trivalent pointed graph in the plane?


\item  Does there exist a trivalent properly colored pointed graph in the sphere?

a)  without additional restrictions?

b)  whose edges are shorter than  $\pi$?

c)   whose edges are shorter than  $\pi / 100$?


\item  Let $ \Gamma$ be a trivalent properly colored pointed graph in the sphere.
For a tile  $\alpha$  denote by   $n(\alpha )$ the number of color changes when 
going along the boundary of~$\alpha$
(for instance, for the tile in Fig.~\ref{ris1.5}, we have $n(\alpha ) = 4 )$.

We consider such graphs that  $n(\alpha )=0$  holds for no tile.

a)  (A joke) Does there exist a graph and a tile such that $n(\alpha )=2007$ ?

b)  (Not a joke at all)  Does there exist a graph and a tile such
that $n(\alpha )=2$?



\begin{figure}
%\begin{picture}(1,1)
%$$\special{em:graph turgor4.bmp }$$
%\end{picture}
\begin{picture}(50,30)
\color{blue}
\path(3,0)(10,10)
\path(0,10)(5,20)(20,20)(25,30)(40,30)
\path(30,20)(40,25)
\path(10,0)(15,10)(40,15)
\color{red}
\path(5,20)(10,10)(10,0)(20,0)
\path(15,10)(30,9)
\path(42,9)(40,15)(30,20)(25,30)
\path(20,20)(10,25)
\color{black}
\put(20,15){$\alpha$}
\put(10,0){\circle*1}\put(10,10){\circle*1}\put(5,20){\circle*1}
\put(15,10){\circle*1}\put(40,15){\circle*1}\put(30,20){\circle*1}
\put(20,20){\circle*1}\put(25,30){\circle*1}
\end{picture}
\caption{}
\label{ris1.5}
\end{figure}


\item  
Let $\Gamma$ be a trivalent pointed graph in the sphere with a proper coloring.
Let $N(\Gamma)$  be the number of tiles  such that $n(\alpha ) = 2$.

Prove that $N(\Gamma) \geq  4$.



\item  Draw a trivalent properly colored pointed graph in
the sphere such that  its edges are shorter than  $\pi$ and
$N(\Gamma) =4, 6, 8, 10 ...$


\item   
Draw a trivalent properly colored pointed graph in the sphere
such that  its edges are shorter than  $\pi$ and $N(\Gamma)=5$.

\item  
Given a finite set of points in the sphere,
under what condition it is the set of vertices of some trivalent
pointed properly colored graph?

(Try to find  a non-trivial necessary or sufficient condition)
\end{enumerate}


\subsection*{Non-isotopic linkages}


Let a graph  be represented by a linkage  (a bar-and-join
mechanism)  in the plane or in the sphere in two different ways
$\Gamma _1$ and $\Gamma_2$.

We say that the position
$\Gamma _1$ is \emph{isotopic} to $\Gamma _2$ if  $\Gamma _1$ can be pulled
to the position  $\Gamma _2$ without self-intersections.
The edges lengths must not change during such a movement.



\begin{enumerate}
\setcounter{enumi}{17}

\item  Draw a linkage with two non-isotopic positions.

\bigskip

\item A cool example (E. Demain)

Redraw the graph (Fig. ~\ref{ris1.6}) in the plane in two
non-isotopic ways. The spider must have equal legs. (I.e., the upper
parts of the legs must be of the same length, the parts from knees
to the feet must be of the same length as well, and  the feet must be
equal.)


\begin{figure}
\begin{picture}(75,55)
\path(5,35)(5,15)(20,2)(40,10)(60,10)(71,25)(73,45)
\put(5,35){\circle*1}\put(5,15){\circle*1}\put(20,2){\circle*1}
\put(40,10){\circle*1}\put(60,10){\circle*1}\put(71,25){\circle*1}
\put(73,45){\circle*1}
\path(13,46)(11,31)(20,17)(40,10)(58,22)(66,37)(62,50)
\put(13,46){\circle*1}\put(11,31){\circle*1}\put(20,17){\circle*1}
\put(58,22){\circle*1}\put(66,37){\circle*1}\put(62,50){\circle*1}
\path(15,52)(21,40)(26,26)(40,10)(53,28)(55,42)(48,53)
\put(15,52){\circle*1}\put(21,40){\circle*1}\put(26,26){\circle*1}
\put(53,28){\circle*1}\put(55,42){\circle*1}\put(48,53){\circle*1}
\path(27,53)(25,40)(36,32)(40,10)(42,30)(38,43)(40,55)
\put(27,53){\circle*1}\put(25,40){\circle*1}\put(36,32){\circle*1}
\put(42,30){\circle*1}\put(38,43){\circle*1}\put(40,55){\circle*1}
\end{picture}
\caption{} \label{ris1.6}
\end{figure}
%$$\special{em:graph turgor7.bmp }$$

\item  Find two non-isotopic positions of four great semicircles
in the sphere. (In other words, the spherical linkage in question
consists of 4 disconnected bars of length~$\pi$.)


\end{enumerate}


\end{document}
