Triangulation of a Planar Map
A graph is called planar if it can be drawn in the plane without
edge crossings. In a drawing of a graph, nodes are identified with points
in the plane and edges with lines connecting the corresponding end nodes.
The edges are not allowed to cross nodes in the drawing.
G=(V,E)
representing a planar map, a triangulation
of G inserts additional edges into the faces of G
such that every face of the resulting graph is a triangle.
LEDA Function for Triangulation of a Planar Map
TRIANGULATE_PLANAR_MAP() computes a triangulation
of a given directed connected graph G=(V,E) representing
a planar map in time O(|V|+|E|).
Example of How To Use TRIANGULATE_PLANAR_MAP()
The following program shows how the function TRIANGULATE_PLANAR_MAP()
can be used.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
We first create a connected planar graph G with four nodes
and four edges. Then we make G a planar map using appropriate
LEDA functions. TRIANGULATE_PLANAR_MAP() adds edges to G
to triangulate it and returns the list
of added edges. We recompute the faces of G and print the
faces of the resulting graph.
#include <LEDA/graph/graph.h>
#include <LEDA/graph/plane_graph_alg.h>
using namespace leda;
int main()
{
graph G;
node n0=G.new_node(); node n1=G.new_node();
node n2=G.new_node(); node n3=G.new_node();
G.new_edge(n0,n1); G.new_edge(n1,n2);
G.new_edge(n2,n3); G.new_edge(n3,n0);
G.make_bidirected(); G.make_planar_map();
face f;
std::cout << "Original faces:" << std::endl;
forall_faces(f,G) {G.print_face(f); std::cout << std::endl;}
std::cout << std::endl;
list<edge> inserted_edges=TRIANGULATE_PLANAR_MAP(G);
G.compute_faces();
std::cout << "Resulting faces:" << std::endl;
forall_faces(f,G) {G.print_face(f); std::cout << std::endl;}
std::cout << std::endl;
return 0;
}
|