TY - JOUR

T1 - An algebraic characterization of planar graphs

AU - Archdeacon, Dan

AU - Paul Bonnington, C.

AU - Little, Charles H.C.

PY - 1995/1/1

Y1 - 1995/1/1

N2 - A cycle in a graph is a set of edges that covers each vertex an even number of times. A cocycle is a collection of edges that intersects each 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 bicycles each form a vector space over the integers modulo two when addition is defined as symmetric difference of sets. In this paper we examine the relationship between the left‐right paths in a planar graph and the cycle space, cocylce space, and bicycle space. We show that planar graphs are characterized by the existence of a diagonal—a double cover by tours that interacts with the cycle space, cocycle space, and bicycle space in a special manner. This generalizes a result of Rosenstiehl and Read that characterized those planar graphs with no nonempty bicycles. © 1995 John Wiley & Sons, Inc.

AB - A cycle in a graph is a set of edges that covers each vertex an even number of times. A cocycle is a collection of edges that intersects each 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 bicycles each form a vector space over the integers modulo two when addition is defined as symmetric difference of sets. In this paper we examine the relationship between the left‐right paths in a planar graph and the cycle space, cocylce space, and bicycle space. We show that planar graphs are characterized by the existence of a diagonal—a double cover by tours that interacts with the cycle space, cocycle space, and bicycle space in a special manner. This generalizes a result of Rosenstiehl and Read that characterized those planar graphs with no nonempty bicycles. © 1995 John Wiley & Sons, Inc.

UR - http://www.scopus.com/inward/record.url?scp=84987467105&partnerID=8YFLogxK

U2 - 10.1002/jgt.3190190209

DO - 10.1002/jgt.3190190209

M3 - Article

AN - SCOPUS:84987467105

VL - 19

SP - 237

EP - 250

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -