Simpler Projective Plane Embedding

Abstract

A projective plane is equivalent to a disk with antipodal points identified. A graph is projective planar if it can be drawn on the projective plane with no crossing edges. A linear time algorithm for projective planar embedding has been described by Mohar. We provide a new approach that takes $O(n^2)$ time but is much easier to implement. We programmed a variant of this algorithm and used it to computationally verify the known list of all the projective plane obstructions.

One application for this work is graph visualization. Projective plane embeddings can be represented on the plane and can provide aesthetically pleasing pictures of some non-planar graphs. More important is that it is highly likely that many problems that are computationally intractable (for example, NP-complete or #P-complete) have polynomial time algorithms when restricted to graphs of fixed orientable or non-orientable genus. Embedding the graph on the surface is likely to be the first step for these algorithms.