Premium
An algebraic characterization of planar graphs
Author(s) -
Archdeacon Dan,
Paul Bonnington C.,
Little Charles H. C.
Publication year - 1995
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.3190190209
Subject(s) - mathematics , planar graph , combinatorics , diagonal , modulo , vertex (graph theory) , vector space , planar , space (punctuation) , algebraic number , graph , cycle basis , discrete mathematics , pure mathematics , geometry , line graph , mathematical analysis , computer science , graph power , computer graphics (images) , operating system
Abstract 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.