Face 2‐Colorable Embeddings with Faces of Specified Lengths. Issue 3 (12th August 2015) - Maenhaut, Barbara; Smith, Benjamin R.
Abstract: Suppose M = m 1, m 2, ..., m r and N = n 1, n 2, ..., n t are arbitrary lists of positive integers. In this article, we determine necessary and sufficient conditions on M and N for the existence of a simple graph G, which admits a face 2‐colorable planar embedding in which the faces of one color have boundary lengths m 1, m 2, ..., m r and the faces of the other color have boundary lengths n 1, n 2, ..., n t . Such a graph is said to have a planar ( M ; N ) ‐biembedding. We also determine necessary and sufficient conditions on M and N for the existence of a simple graph G whose edge set can be partitioned into r cycles of lengths m 1, m 2, ..., m r and also into t cycles of lengths n 1, n 2, ..., n t . Such a graph is said to be ( M ; N ) ‐decomposable.