Open Graph Drawing Framework
current version:
v.2012.07 (Sakura)
     

Planarization of a connected graph

Topic

Compute a planar representation of the graph with few dummy nodes (representing crossings). We assume the graph to be connected.

Source-Code

#include <ogdf/basic/Graph.h>
#include <ogdf/planarity/PlanRep.h>
#include <ogdf/planarity/SubgraphPlanarizer.h>
#include <ogdf/planarity/FastPlanarSubgraph.h>
#include <ogdf/planarity/VariableEmbeddingInserter.h> 
 
using namespace ogdf;
 
int main()
{
	Graph G;
	G.readGML("test.gml");
	PlanRep PR(G);
 
	int crossNum;
	SubgraphPlanarizer SP;
	SP.setSubgraph(new FastPlanarSubgraph());
	SP.setInserter(new VariableEmbeddingInserter()); 
	SP.call(PR,0,crossNum);
 
	cout << crossNum << endl;
	PR.writeGML("plan.gml");
 
	return 0;
}

Explanation

We first declare a Graph G and load it from the GML-file test.gml. Afterwards we declare a planar representation PR of G (PlanRep PR(G);). PlanRep is a special kind of GraphCopy particularly suitable for planarizations, i.e., insertions of dummy nodes representing edge crossings.

We then generate a SubgraphPlanarizer, which is a special form of a CrossingMinimizationModule. It planarizes the given graph by first computing a large planar subgraph, and adding the removed edges later on. Both steps are configurable, i.e., you can choose between different modules which perform them (SP.setSubgraph() and SP.setInserter()). The modules specified in this example (FastPlanarSubgraph and VariableEmbeddingInserter) are OGDF's standard selection, i.e., they are used if the modules are not explicitly specified.

Each CrossingMinimizationModule can be called like SP.call(PR,0,crossNum), specifying the PlanRep which is used for the planarization (PR knows about the original graph G through its constructor), 0 is the index of the (single) connected component of G that shall be planarized. (If there would be k components, we would have to call the planarizer k times, once for each component; a PlanRep always only represents a single connected component). crossNum is a variable (call by reference) which is set to the number of crossings/dummy nodes that were inserted.

Finally we write the number of crossings to the console and store the planarized graph as a GML file.

Notice that we do not delete the objects allocated with new; these objects are deleted automatically by SP. As a general rule, modules passed to module options must be allocated with new and may not be deleted.

 
tech/howto/plz.txt · Last modified: 2010/09/30 10:19 (external edit)
This page is driven by DokuWiki