𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An algebraic characterization of planar graphs

✍ Scribed by Dan Archdeacon; C. Paul Bonnington; Charles H. C. Little

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
773 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

An algebraic characterization of project
An algebraic characterization of projective-planar graphs
✍ Lowell Abrams; Daniel C. Slilaty πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 114 KB

## Abstract We give a detailed algebraic characterization of when a graph __G__ can be imbedded in the projective plane. The characterization is in terms of the existence of a dual graph __G__\* on the same edge set as __G__, which satisfies algebraic conditions inspired by homology groups and inte

Characterizing planarity using theta gra
Characterizing planarity using theta graphs
✍ Archdeacon, Dan; S?rοΏ½n?, Josef πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 87 KB

A theta graph is a homeomorph of K 2,3 . In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated

An algebraic theory of graph factorizati
An algebraic theory of graph factorization
✍ Andrew Vince πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 136 KB

An algebraic theory of graph factorization is introduced. For a factor h, a graph G(h) is constructod whose structure contains information about h-factorability. The l-factorable and cycle factorable graphs over Z2 are characterized, and properties of the corresponding graph G(h) are obtained.

An algorithm for drawing planar graphs
An algorithm for drawing planar graphs
✍ Bor Plestenjak πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 382 KB πŸ‘ 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

Characterizing 3-connected planar graphs
Characterizing 3-connected planar graphs and graphic matroids
✍ Manoel Lemos; Talmage James Reid; Haidong Wu πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 98 KB

## Abstract A well‐known result of Tutte states that a 3‐connected graph __G__ is planar if and only if every edge of __G__ is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give n