# Polyominoes, Gray Codes and Venn Diagrams

## Frank Ruskey, University of Victoria

A polyomino is a configuration of unit squares in the
plane. Squares are joined along their edges and the
configuration may not contain holes. In this talk we
consider two topics on polyominoes:
Gray codes for polyominoes and Venn diagrams
of minimum area constructed from polyominoes.

The Gray codes that we consider are for column-convex
polyominoes, which are those whose intersections
with vertical lines are connected. In the code successive
polyominoes differ by the movement of one square.
These Gray codes have interesting connections with certain
classical distributive lattices studied in algebraic combinatorics,
particularly with regard to questions of rank unimodality.

A Venn diagram is a collection of n simple closed curves
(e.g., the outlines of polyominoes) whose 2^n possible interior
intersections are all non-empty and connected.
A Venn diagram whose curves are polyominoes has minimum area
if every intersection of curve interiors is a unit square,
with the exception of the empty set. Previously they were
known to exist only for n <= 4 polyomino curves;
we give examples showing that they exist up to n=7 polyomino
curves, and give an approximation algorithm to construct
them with close to minimum area for all n.

This is joint research with my graduate student Stirling Chow.