next up previous contents index
Next: Parameterized Planar Maps ( Up: Graphs and Related Data Previous: Parameterized Ugraphs ( UGRAPH   Contents   Index


Planar Maps ( planar_map )

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.

#include < LEDA/planar _map.h >

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(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(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.


next up previous contents index
Next: Parameterized Planar Maps ( Up: Graphs and Related Data Previous: Parameterized Ugraphs ( UGRAPH   Contents   Index
LEDA research project
2000-02-09