19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

# Quadrangulations on 3-colored point sets with Steiner points

Presented by Prof. Atsuhiro NAKAMOTO

Type: Oral presentation

Track: General session

## Content

Let $P$ be a point set on the plane, and consider whether $P$ is {¥em quadrangulatable¥/}, that is, whether there exists a 2-connected bipartite plane graph $G$ with edge edge straight segment such that $V(G)=P$, that the outer cycle of $G$ coincides with Conv($P$), that each finite face of $G$ is quadrilateral. It is easy to see that it is possible if an even number of points of $P$ lie on Conv($P$). Hence we give a $k$-coloring of $P$ and consider the same problem, avoiding edges joining two vertices of $P$ with the same color. In this case, we always assume that the number of the points of $P$ lying on Conv($P$) is even and any two consecutive points on Conv($P$) have distinct colors. However, there is a 2-colored non-quadrangulatable point set $P$. So we introduce a {¥em Steiner point}, which can be put in any position of the interior of Conv($P$) and may be colored by any color of the $k$ colors. When $k=2$, Alverez et al. proved that if a point set $P$ on the plane consists of $¥frac n2$ red and $¥frac n2$ blue points in general position, then adding Steiner points $Q$ with $|Q| ¥leq ¥lfloor ¥frac {n-2}6 ¥rfloor + ¥lfloor ¥frac n4 ¥rfloor +1$,
$P ¥cup Q$ is quadrangulatable, but there exists a non-quadrangulatable 3-colored point set for which no matter how many Steiner points are added. In this paper, we define the winding number for a 3-colored point set $P$, and prove that a 3-colored point set $P$ in general position with a finite number of Steiner points $Q$ added
is quadrangulatable if and only if the winding number of $P$ is zero. When $P ¥cup Q$ is quadrangulatable, we prove $|Q| ¥leq ¥frac {7n+34m-48}{18}$, where $|P|=n$ and the number of points of $P$ in Conv($P$) is $2m$.

## Place

Location: Bled, Slovenia

Address: Best Western Hotel Kompas Bled