Premium
Face 2‐Colorable Embeddings with Faces of Specified Lengths
Author(s) -
Maenhaut Barbara,
Smith Benjamin R.
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21902
Subject(s) - mathematics , combinatorics , planar graph , embedding , graph , book embedding , planar straight line graph , planar , outerplanar graph , simple (philosophy) , discrete mathematics , 1 planar graph , pathwidth , line graph , computer science , artificial intelligence , philosophy , computer graphics (images) , epistemology
Suppose M = m 1 , m 2 , ... , m rand N = n 1 , n 2 , ... , n tare 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 lengthsm 1 , m 2 , ... , m rand the faces of the other color have boundary lengthsn 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 lengthsm 1 , m 2 , ... , m rand also into t cycles of lengthsn 1 , n 2 , ... , n t . Such a graph is said to be ( M ; N ) ‐decomposable.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom