Presented by: 
Ben Smith, UQ
Date: 
Tue 26 Nov, 3:00 pm - 4:00 pm
Venue: 
Room 442, Building 67

A face 2-colourable planar embedding of a simple graph G in which the black faces have boundary cycles of lengths m1, m2, ... , mr and the white faces have boundary cycles of lengths n1, n2, ... , nt is said to be a biembedding of the cycle lists M = m1, m2, ... ,mr and N = n1, n2, ... , nt. We use Euler's classic formula relating the number of vertices, edges and faces in a planar embedding to derive necessary and sufficient conditions for the existence of such an embedding given two arbitrary lists of cycle lengths. We will also discuss the somewhat surprising result that these conditions are exactly equivalent to those required for the existence of a simple (not necessarily planar) graph G which has a decomposition into cycles of lengths m1, m2, ... ,mr and into cycles of lengths n1, n2, ... ,nt (with three `small case' exceptions).