Using G & G with Projective Maps
Last update=16 May, 2006
A projective map is an embedding of a graph on the projective plane. Above is a typical projective map window containing an embedding of the Petersen graph on the projective plane. The projective plane is represented as a disc in which antipodal points have been identified. Edges wrap around the projective plane when they cross the boundary of the disc. A projective map window shows the disc in the central region, surrounded by a larger blue region, in order to make it easier to edit the graph, and to visualize the faces, and the wrapping of the edges. The vertices of the projective map all appear in the disc. Copies of them appear as "ghost" nodes in the outer region. Projective maps are required to be 2-connected, 2-cell embeddings at all times. An essential cycle of a projective map is a cycle that cannot be contracted to a point within the projective plane (therefore it must cross the boundary of the disc an odd number of times). Loops and multiple edges are supported to some extent. A vertex v can have up to one loop, if it forms an essential cycle. Similarly, vertices u and v can be connected by up to two multiple edges, so long as they form an essential cycle.
An algorithm to determine whether an arbitrary graph is projective has not yet been implemented in G&G. This will appear in a future release.
Projective Map Functions Available in G&G 3.2
Dual MapConstruct the dual map whose vertices correspond to the faces of the original map.
Graph LayoutGiven a projective map, find a layout of the vertices with no edges crossing. This function is currently somewhat rudimentary. It will be improved in a later release.
Medial GraphThe faces of a projective map X are determined by the cyclic ordering of the edges incident on each node. This is called a "rotation system" for the graph. The projective plane is an unorientable surface. The medial graph is formed by representing each vertex and edge of X by a new vertex. Loops are represented by 2 new vertices. Cycles in the medial graph are used to encode the rotation system of X.
Double CoverIf two copies of a projective plane, represented by a disc, are glued together along the boundaries of the discs, with corresponding points glued together, the result is a sphere. Each point of the projective plane corresponds to two points of the sphere. So the sphere is a double cover of the projective plane. If a projective map X is drawn on the projective plane when the discs are glued together, the result is a graph drawn on the sphere -- a sphere map -- that is a double cover of X. Corresponding to every vertex and edge of X are two vertices and two edges of the double cover. Notice from the diagram above that the Dodecahedron is a double cover of the Petersen graph.
Automorphism GroupThe automorphism group Aut(X) of a projective map is the group of permutations of the vertices that preserves the rotation system of X. It is computed via the double cover.
Truncate CornersEvery vertex of X is truncated -- that is, if deg(v)=k, then v is replaced by a cycle of k new vertices. The result is a new projective map. Back to the Groups & Graphs home page.