Directedness, Duality, and Parity Conditions for Embedded Graphs

Abstract

Parity conditions for walks in graph-encoded maps, also known as gems, have been used to characterize orientability and bipartiteness for cellularly embedded graphs. We show that seven parity conditions for graph-encoded maps can be used to characterize various properties of cellularly embedded graphs and their related graphs. The seven conditions can be associated with points in the Fano plane, and any three distinct points in the Fano plane correspond to a theorem relating their associated conditions. One of the seven conditions corresponds to the existence of an orientation of the embedded graph such that the embedding is a directed embedding. In our work regarding directed embeddings we also characterize when a mixed graph and a collection of its closed directed walks can be extended to a directed embedding of an orientation of the mixed graph such that the collection of closed directed walks is a subcollection of the facial walks. Furthermore, we characterize when such a directed embedding can be chosen to be orientable. The seven parity conditions for gems relate to properties of embedded graphs and their corresponding graphs generated by the standard operations of duality and Petrie duality. A generalization of duality to partial duality was introduced by Chmutov in 2009. We make progress towards finding a set of properties that uniquely characterize Chmutov's partial duality as an operation on edge-labeled cellularly embedded graphs.