Edge Insertion Modules ( EdgeInsertionModule )

Baseclasses

Definition

The class EdgeInsertionModule is the base class for edge insertion modules. An edge insertion module gets as input a planarized graph PG, which is a copy of a graph G, and a list of edges e₁,..., e_k $\in$ G. It inserts e₁,..., e_k into PG by replacing edge crossings with dummy nodes.

Edge insertion modules are used for computing a planarization with a planar subgraph. The edges that are not in the planar subgraph are reinserted by means of an edge insertion module (see Section Planarization with Planar Subgraph).

Input and Output Parameters

input parameters:	planar map	in_planar_map=1
	edge list	in_edge_list=2
output parameter:	planarized graph	out_planarized_graph=1

The integer constants in_planar_map, in_edge_list and out_planarized_graph 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 Edge Insertion Modules

An implementation of an edge insertion module must override the protected method do_call(PG, list<edge>& e_insert), which gets as input a planarized graph PG, and a list of edges e$\_$insert = e₁,..., e_k, which must be inserted.

The planarized graph PG is a copy of G, and e₁,..., e_k $\in$ G. For each edge e_i, the implementation inserts a chain of edges starting at copy(source(e_i)) and ending at copy(target(e_i)) that leads over dummy nodes. The dummy nodes are new nodes resulting from splitting an edge, which will represent edge crossings in a drawing of the graph.

The class PlaneGraphCopy stores these chains and provides methods (split, new_edge_chain) for reinserting edges.

#include < AGD/EdgeInsertionModule.h >

Initialization

EdgeInsertionModule

I

initializes an edge insertion module.

Operations

Standard Interface

bool	I.check(const PlaneGraphCopy& G, leda_list<leda_edge>& e_insert, AgdKey& p)
		returns true if G satisfies the precondition of I. Otherwise, false is returned and p contains a property that is not satisfied.
void	I.call(PlaneGraphCopy& PG, leda_list<leda_edge>& e_insert)
		calls the edge insertion module for plane graph copy PG.

Protected Overridables to Implement Functionality

void	I.do_call(PlaneGraphCopy& G, leda_list<leda_edge>& e_insert)
		implements the edge insertion module for plane graph copy PG, and list of edges e_insert.