# Bled'11 - 7th Slovenian International Conference on Graph Theory

19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

# 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

More