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.
- The arrow tool is for selecting and moving nodes.
- The pencil is for editing the graph, edges are added or deleted as the pencil clicks from node to node. The graph must always remain 2-connected when edges are deleted.
- The fat pencil is for editing the bold subgraph. It adds or deletes thick edges as the mouse is clicked
- The sputnik creates a new node attached to all currently selected nodes, at the point where the mouse is clicked. It is a good idea to attach a new node to at least 3 nodes, or the new node may not be placed in the face you want.
- The bullet tool cannot be used with projective maps, as the resulting graph would not be 2-connected.
- The hand is not supported.
- The flag is not supported.
- The thermometer is not supported.
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 Map
Construct the dual map whose vertices correspond to the faces of the original map.Graph Layout
Given 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 Graph
The 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 Cover
If 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 Group
The 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 Corners
Every 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.