AN ALGEBRAIC CHARACTERIZATION OF PLANAR GRAPHS

A cycle in a graph is a set of edges that covers each vertex an even n umber of times. A cocycle is a collection of edges that intersects eac h cycle in an even number of edges. A bicycle is a collection of edges that is both a cycle and a cocycle. The cycles, cocycles, and bicycle s each form a vector space over the integers module two when addition is defined as symmetric difference of sets. In this paper we examine t he relationship between the left-right paths in a planar graph and the cycle space, cocycle space, and bicycle space. We show that planar gr aphs are characterized by the existence of a diagonal-a double cover b y tours that interacts with the cycle space, cocycle space, and bicycl e space in a special manner. This generalizes a result of Rosenstiehl and Read that characterized those planar graphs with no nonempty bicyc les. (C) 1995 John Wiley & Sons, Inc.