Face 2‐Colorable Embeddings with Faces of Specified Lengths |
| |
Authors: | Barbara Maenhaut Benjamin R Smith |
| |
Institution: | SCHOOL OF MATHEMATICS AND PHYSICS, THE UNIVERSITY OF QUEENSLAND, AUSTRALIA |
| |
Abstract: | Suppose and 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 and the faces of the other color have boundary lengths . Such a graph is said to have a planar ‐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 and also into t cycles of lengths . Such a graph is said to be ‐decomposable. |
| |
Keywords: | graph embedding graph decomposition |
|