it is also not true of any other nonplanar graph. provided another proof, based on algebraic topology. He uses a slightly different formulation of the planarity criterion, according to which a graph is planar if and only if it has a set of (not necessarily simple) cycles covering every edge exactly twice, such that the only nontrivial relation among these cycles in is that their sum be zero. If this is the case, then leaving any one of the cycles out produces a basis satisfying Mac Lane's formulation of the criterion. If a planar graph is embedded on a sphere, its face cycles clearly satisfy Lefschetz's property. Conversely, as Lefschetz shows, whenever a graph G has a set of cycles with this property, they necessarily form the face cycles of an embedding of the graph onto the sphere. Application used Mac Lane's planarity criterion as part of a parallel algorithm for testing graph planarity and finding planar embeddings. Their algorithm partitions the graph into triconnected components, after which there is a unique planar embedding (up to the choice of the outer face) and the cycles in a 2-basis can be assumed to be all the peripheral cycles of the graph. Ja'Ja' and Simon start with a fundamental cycle basis of the graph (a cycle basis generated from a spanning tree by forming a cycle for each possible combination of a path in the tree and an edge outside the tree) and transform it into a 2-basis of peripheral cycles. These cycles form the faces of a planar embedding of the given graph. Mac Lane's planarity criterion allows the number of bounded face cycles in a planar graph to be counted easily, as the circuit rank of the graph. This property is used in defining the meshedness coefficient of the graph, a normalized variant of the number of bounded face cycles that is computed by dividing the circuit rank by , the maximum possible number of bounded faces of a planar graph with the same vertex set . References . . . . . Algebraic graph theory Planar graphs