An instance M of the data type planarmap 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.
#include < LEDA/graph/planar_map.h >
|planar_map||M(const graph& G)||creates an instance M
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.
|edge||M.new_edge(edge e1, edge e2)|
|inserts the edge
e = (source(e1), source(e2))
and its reversal into M
and returns e
Precondition e1 and e2 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(const list< edge> & el)|
|splits the face bounded by the edges in el
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.|
Planar maps are implemented by parameterized directed graph. 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.