Face 2‐Colorable Embeddings with Faces of Specified Lengths. Issue 3 (12th August 2015)

• Record Type: Journal Article
• Authors: Maenhaut, Barbara; Smith, Benjamin R.
• Is Part Of: Journal of graph theory. Volume 82:Issue 3(2016)
• Page Start: 296
• Page End: 311
• Publication Date: 2015-08-12
• Subjects: graph embedding -- graph decomposition; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21902
• Languages: English
• ISSNs: 0364-9024

Abstract

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.