Planarization Modules ( PlanarizerModule )

Baseclasses

Definition

The class PlanarizerModule is the base class for planarization modules. A planarization module transforms a graph G into a planar graph PG by replacing edge crossings with dummy nodes, and computes a combinatorial embedding of PG.

Input and Output Parameters

input parameter:	graph	in_graph=1
output parameter:	planarized graph	out_planarized_graph=1

The integer constants in_graph and out_planarized_layout denote the positions in the input and output parameter lists. The values can be used to reference the desired parameter when setting the pre- and postcondition.

Implementation of Planarization Algorithms

An implementation of a planarization module must override the protected method do_call(G,PG), which gets as input a graph G = (V, E) and produces as output a planar graph PG = (V $\cup$ V_d, E'). It replaces a set of edges E_r $\subset$ E by chains of edges leading over dummy nodes $\in$ V_d. Each dummy node is a node of degree 4, and the output graph PG represents a planar map.

In particular, an edge e = (v, w) $\in$ E_r is replaced with a chain e₁ = (v₁, v₂),..., e_k = (v_k, v_{k + 1}), where v₁ = v, v_{k + 1} = w, and v_i $\in$ V_d for all 2 < = i < = k. The corresponding chain of edges is stored in PG, i.e., PG.chain(original(e)) = e₁,..., e_k. Furthermore, tho following must hold:

• degree(v) = 4 for all v $\in$ V_d, and E_r = E $\setminus$ E'.
• Let E_d = E' $\setminus$ E be the set of inserted new edges.

  Then, there must be a mapping $\varphi$ : E_d$\to$E_r with $\;\stackrel{-1}{\varphi}\;$(e) = chain(e) for all e $\in$ E_r.

The implementation must also embed the output graph, i.e., the combinatorial embedding must be given by the clockwise ordering of the edges in all adjacency lists.

#include < AGD/PlanarizerModule.h >

Initialization

PlanarizerModule

P

initializes a planarization module.

Operations

Standard Interface

bool	P.check(const GraphCopy& G, AgdKey& p)
		returns true if G satisfies the precondition of P. Otherwise, false is returned and p contains a property that is not satisfied.
void	P.call(const leda_graph& G, PlaneGraphCopy& PG)
		calls the planarization module for graph PG. Stores the planarization in PG, i.e., for every edge e $\in$ G the ordered list of corresponding edges chain(e) in PG.

Protected Overridables to Implement Functionality

void	P.do_call(const leda_graph& G, PlaneGraphCopy& PG)
		implements the planarization algorithm for graph G. Stores the planarization in PG, i.e., for every edge e $\in$ Er the ordered list of corresponding edges chain(e) in PG.