\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{hyperref}
\usepackage{graphicx}

\usepackage{amsmath,amssymb}
\newcommand{\No}{N$^{\circ}$}

\newcommand{\R}{\mathbb{R}}
\newcommand{\binomial}[2]{\left(\begin{array}{c} #2\\#1\end{array}\right)}



\begin{document}
\title{Barbados 2012}
\date{Friday February 10th}
\author{Wrap-up session}
\maketitle

\section{Touching boxes graphs}
{\bf Dave R., Dave B., Bill, Will, Sue, Fabrizio, Stephen, Laurie, Beppe}

\paragraph{Problem.} Drawing graphs where vertices are boxes and there is an edge if two boxes touch. 
The problem is considered in 3D. 

\paragraph{Previous results} Thomassen proved in 1984 that every planar graph has a strict box drawing (strict means that
touching boxes must have positive area for them to be connected by an edge)

Felsner proved last year (socg) proved that every planar graph has a cube drawing (but the drawing
is not necessarily strict).

\paragraph{Results.} ~

{\bf Thm.} A strict unit cube drawable graph with $n$ vertices has $7n-\sqrt[3]{n}$ edges which is asympotically tight. 

{\bf Thm.} Every planar partial 3-tree has a strict cube drawing. (A planar partial 3-tree is a graph that can be augmented
to be a planar 3-tree. This is equivalent to be a graph of tree width at most 3.) 

As a side result, a much simpler proof of Thomassen's result was also obtained (bases on Schnider trees and canonical ordering). 

\section{Computational aesthetics}
{\bf Raimund, Brian, Paul}

\paragraph{Problem.} Given a (convex) polygon, find a curve approximating the polygon from the inside and that is nice

Different approaches where considered (and using splines is a classic one).

\paragraph{Barriers functions.}~

Instead of considering the polygon, we consider the arrangement of the lines supporting its edges. 
This arrangement is the 0-set of the polynomial $p=\Pi_i \ell_i$ where $\ell_i$ is the equation of the
lines. One approach is to draw $p(x,y)=\epsilon$ 

Note that $\log p=\sum \log \ell_i$ and the $\log \ell_i$ are the barriers functions (up to their
sign).

More generally one can choose $\sum \phi( \ell_i)$ with $\phi$ convex (?) and taking value infinity
at 0, such as $g(u)=1/u^2$ or $\frac{1}{1-{e}^u}$.




\paragraph{Simulation of physical processes.}~

Repeatedly choose a random direction $d$ and cut the polygon by a line normal to $d$ so that the area of the
polygon is reduced by $\alpha_i<1$ (which depend on the time) such that $\Pi \alpha_i=1/2$.


\section{Red-blue trees}
{\bf Tamara, Nishat, Bill, Marc, Fabrizio, Beppe, (Henk ?).}

\paragraph{Original question:}
Given a bicolor tree (vertices are colored) such that every edge is
bicolored.
Is there an universal bicolored point set that allows to embed any tree.


\paragraph{Results.}
 
If the tree is balanced (in any subtree, $|\sharp$ of blue vertices -
$\sharp$ red $| \leq 1$, it can be draw on a point set in convex
position
with alternating colors. Works even for non binary tree.

For unbalanced tree, there is a $2n$ point set using book embeddings

Conjecture: adding $n/3$ points is enough to balance the tree.

Corollary: $4n/3$ universal point set.

Given a colored (non binary) 
tree and a colored convex point set, decide if it is embedable is NP hard.


\section{Resilience problem}

{\bf Hyo-Sil, Dominique, Helmut, Sylvain, Christian, Marc, Sue, Bill}

\paragraph{Problem.} Given an arrangement of disks in $\R^2$
and two points $s$ and $t$, find a path from $s$ to $t$ than minimize the number of disks crossed
($\sharp$ disks you have to removed so that the path is free).

\paragraph{Previous work.} This problem is NP-hard for line segments [Helmut].(3 distinct proofs by
David Kirkpatrick etal.;  Helmut, Hyo-Sil et al.; Christian et al. 3-approximation algo by D. Kirkpatrick.

\paragraph{Results.} No breakthrough but partial results. 

Note the disks containing $s$ and $t$ can be removed since they have to be traversed. 

{\bf Lemma.} Given a set of disks, minimizing the number of disks to remove so that the complement of all
he disks become connected is NP-hard. 

{\bf Proof.} Reduction from Feedback vertex cover. The (mild) difficulty is to prove that given any planar graph it
can be covered by a polynomial number of disks with disks at the vertices and disks (with
high enough multiplicity) covering the edges (but only one piece at a time). This can be done by first
embedding the graph in a 2n by 2n grid and arguing that we can use polynomially many disks. 

{\bf Lemma.}  Given a plane graph and $s$ and $t$ in two cells, we can determine in polynomial time the minimum number of
vertices to remove so that the cells of $s$ and $t$ get connected. 

{\bf Proof.} Connect $s$ (resp.  $t$) to all the vertices in the cell it lies. For every cells,
connect all the vertices of that cell. FInd the shortest path from $s$ to $t$, The vertices on the
paths is the minimal set of vertices to remove. 

{\bf Lemma.} Given a set of disks whose intersection graph (vertex at each disk center and edge
connecting any two intersecting disks) is a  plane graph (the actual drawing is planar), we can
solve the problem in polynomial time by applying the previous lemma. 


\section{ Simultaneous embedding}
{\bf Fabrizio, Will}

\paragraph{Problem.} Given two planar graphs $G_1$ and $G_2$ with $n$ vertices, find two straight
line plane drawing with the same points. 


\paragraph{Previous work.} It is not known whether such a drawing always exists.

\paragraph{Relaxation of the problem.} Assume that $G_1$ has $n$ vertices and that  $G_2$ has $k<n$
vertices.  More precisely, how large can we choose $k$ so that we can ensure simultaneous
embedding. 

\paragraph{Even more relaxed:-)} Curved edges are allaowed and we require that if between two vertices
in the drawings, there is an edge between these vertices in the two graphs, then the two edges are
the same (this makes senses since the edge can be curved). 

\paragraph{Results.} If $k=\lfloor n/6\rfloor$, there is a mapping of the vertices so that the two
graph have no common edges. The problem is then solved because any planar graph and any set of
points, the graph can be drawn planar by considering sufficiently complicated edges. 


\section{Touching triangles graph}
{\bf Nishat, Stephen, Jyoti}

\paragraph{Problem.} Given a graph, draw the vertices has triangle and two triangles sharing a
segment of non-zero length represent an edge. The  outer face may not be a triangle

\paragraph{Results.} We can do it for triconnected cubic graphs. 

The proof is constructive, starting from $K_4$, then iteratively add vertices and modify the
corresponding  triangles graph reprensentation. 

We also considered arrangement graphs but without success except for the special case of parabolic
grid graph. 



\section{Distance between piecewise linear functions}
{\bf Oliver Boris, Guillaume, Christian Eric}

For more  details see the file distance.pdf

\paragraph{Problem.} Given two triangulations of a convex polygon in the plane. 
Let $f$ be a piecewise linear function, linear on each blue triangle.
and $g$ linear on red triangles.
Compute the distance between $f$ and $g$
that is $\sqrt{\int(f-g)^2}$
can be solved in $O(n\log^4 n)$ time.

Question: do it for $L_1$ norm
$\sqrt{\int|f-g|}$ in subquadratic time.

\paragraph{Results.}

Potential result: $O(n^{2-\frac{1}{\kappa}})$ with $\kappa$ is
  some integer, may be 20.

We group the red triangles by group of size $l$.

A (blue) triangle can be represented by a point in $\R^9$.

A red triangle induces a subdivision in $\R^9$ 
(using 33 surfaces of degree 1, 2, or 3) to describe the intersection
of a generic (blue) triangle.

For each group we compute the arrangement of $33l$ surfaces in $\R^9$
of size $\R^9$ and with a point location structure of size $\R^{14}$.
For each cell we can compute a ratioanl function of degree $l$.

Then we locate all blue triangles in that sata structure and make
parallel evaluation of the rational function for triangles lying in
the same cell.


\section{Red-blue point separation}
{\bf Boris, Xavier, Marc, Tamara, Christian}

\paragraph{Problem.} Given a set of red and blue points, can they be separated by $k$ lines, that is
find  $k$ lines such that is every pair of red-blue points is separated by a line.

\paragraph{Result.} Several  conjectures that were somewhat shattered by Marc following example  of 3 blue points and arbitrarily many red points, such that they 
cannot be separated them with 2 lines, but any proper subset (ie removing \emph{any} point) can be
separated by 2 lines). 


%\section{Universal set of points for bi-colored binary trees}
%
%\paragraph{Problem.} Family of binary trees with $n_r$ red vertices and $n_b$ blue vertices.
%Is there a bicolored universal point set for straight line drawing of such binary trees?
%
%\paragraph{Previous results.} Known if $n_r=1$.
%Known if the binary trees contains only degree 1 or 3 nodes.



\end{document}