Definition
An instance M of the data type planar_map is the combinatorial embedding of a planar graph, i.e., M is bidirected (for every edge (v,w) of M the reverse edge (w,v) is also in M) and there is a planar embedding of M such that for every node v the ordering of the edges in the adjacency list of v corresponds to the counter-clockwise ordering of these edges around v in the embedding.
Creation
| planar_map | M(graph G); | creates an instance M of type planar_map and initializes it to
the planar map represented by the directed graph G.
Precondition: G represents a bidirected planar map, i.e. for every edge (v,w) in G the reverse edge (w,v) is also in G and there is a planar embedding of G such that for every node v the ordering of the edges in the adjacency list of v corresponds to the counter-clockwise ordering of these edges around v in the embedding. |
|
Operations
| edge | M.new_edge(edge e1, edge e2) | |
| inserts the edge e=(source(e_1),source(e_2))
and its reversal into M and returns e.
Precondition: e_1 and e_2 are bounding the same face F. The operation splits F into two new faces. |
||
| face | M.del_edge(edge e) | deletes the edge e and its reversal from M. The two faces adjacent to e are united to one new face which is returned. |
| edge | M.split_edge(edge e) | splits edge e=(v,w) and its reversal r=(w,v) into edges (v,u), (u,w), (w,u), and (u,v). Returns the edge (u,w). |
| node | M.new_node(list<edge> el) | splits the face bounded by the edges in el by
inserting a new node u and connecting it to all
source nodes of edges in el.
Precondition: all edges in el bound the same face. |
| node | M.new_node(face f) | splits face f into triangles by inserting a new node u and connecting it to all nodes of f. Returns u. |
| list<edge> | M.triangulate() | triangulates all faces of M by inserting new edges. The list of inserted edges is returned. |
Implementation
Planar maps are implemented by parameterized directed graphs. All operations take constant time, except for new_edge and del_edge which take time O(f) where f is the number of edges in the created faces and triangulate and straight_line_embedding which take time O(n) where n is the current size (number of edges) of the planar map.