An algebraic characterization of planar graphs

Dan Archdeacon, C. Paul Bonnington, Charles H.C. Little

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)237-250
Number of pages14
JournalJournal of Graph Theory
Volume19
Issue number2
DOIs
Publication statusPublished - 1 Jan 1995
Externally publishedYes

Cite this