Simpler Projective Plane Embedding.
Jianping Roth, Wendy J. Myrvold · 2005
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 [20]. We provide a new approach that takes O(n 2 ) time is but much easier to implement. 1 Description of the problem A graph G consists of a set V of vertices and a set E of edges, each of which is associated with an unordered pair of vertices from V . Throughout this paper, n denotes the number of vertices of a graph, and m is the number of edges. A graph is embeddable on a surface M if it can be drawn on M without crossing edges. A graph can be used to model many things. Some examples with applications in computer science include modelling program structure, networks, or how documents on the web are linked together using hyperlinks. A graph visualization tool can help researchers to better understand the structure of such thin...