# OpenGraph DrawingFramework

v.2012.07

ogdf::EmbedderMinDepth Class Reference

Planar graph embedding with minimum block-nesting depth. More...

#include <ogdf/planarity/EmbedderMinDepth.h>

Inheritance diagram for ogdf::EmbedderMinDepth:

List of all members.

## Public Member Functions

EmbedderMinDepth ()
Computes an embedding of G with minimum depth.
Public Member Functions inherited from ogdf::EmbedderModule
EmbedderModule ()
Initializes an embedder module.
virtual ~EmbedderModule ()
Calls the embedder algorithm for planarized representation PG.
Public Member Functions inherited from ogdf::Module
Module ()
Initializes a module.
virtual ~Module ()
Public Member Functions inherited from ogdf::Timeouter
Timeouter ()
timeout is turned of by default
Timeouter (double t)
timeout is set to the given value (seconds)
Timeouter (bool t)
timeout is turned off (false) or on (true) (with 0 second)
Timeouter (const Timeouter &t)
~Timeouter ()
bool isTimeLimit () const
returns whether any time limit is set or not
void timeLimit (double t)
sets the time limit for the call (in seconds); <0 means no limit.
void timeLimit (bool t)
shorthand to turn timelimit off or on (with 0 seconds)
double timeLimit () const
returns the current time limit for the call

## Private Member Functions

int bottomUpTraversal (const node &bT, const node &cH)
Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex $$v \neq c in \a bT$$ is set to 1 if $$v \in M_{bT}$$ and to 0 otherwise.
void computeBlockGraphs (const node &bT, const node &cH)
Computes recursively the block graph for every block.
void embedBlock (const node &bT)
Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
void embedBlock (const node &bT, const node &cT, ListIterator< adjEntry > &after)
Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.
void topDownTraversal (const node &bT)
Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = $$\max_{v \in V_B, v != c} m_B(v)$$ and M2 = $${c \in V_B \ {v} | m_B(c) = m2}$$.

## Private Attributes

NodeArray< GraphblockG
NodeArray< EdgeArray< edge > > eBlockEmbedding_to_eH
NodeArray< EdgeArray< edge > > eH_to_eBlockEmbedding
NodeArray< List< node > > M2
NodeArray< List< node > > M_B
EdgeArray< int > m_cB
NodeArray< int > minDepth
NodeArray< NodeArray< node > > nBlockEmbedding_to_nH
NodeArray< List< adjEntry > > newOrder
NodeArray< NodeArray< node > > nH_to_nBlockEmbedding
NodeArray< NodeArray< int > > nodeLength
BCTreepBCTree
NodeArray< StaticSPQRTree * > spqrTrees
NodeArray< bool > treeNodeTreated

## Detailed Description

Planar graph embedding with minimum block-nesting depth.

See paper "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for details.

Definition at line 61 of file EmbedderMinDepth.h.

## Constructor & Destructor Documentation

 ogdf::EmbedderMinDepth::EmbedderMinDepth ( )
inline

Definition at line 65 of file EmbedderMinDepth.h.

## Member Function Documentation

 int ogdf::EmbedderMinDepth::bottomUpTraversal ( const node & bT, const node & cH )
private

Bottom-up-traversal of bcTree computing the values m_{cT, bT} for all edges (cT, bT) in the BC-tree. The length of each vertex $$v \neq c in \a bT$$ is set to 1 if $$v \in M_{bT}$$ and to 0 otherwise.

Parameters:
 bT is a block vertex in the BC-tree. cH is a vertex in the original graph G.
Returns:
Minimum depth of an embedding of bT with cH on the external face.
virtual

Computes an embedding of G with minimum depth.

Parameters:
 G is the original graph. adjExternal is assigned an adjacency entry in the external face.

Implements ogdf::EmbedderModule.

 void ogdf::EmbedderMinDepth::computeBlockGraphs ( const node & bT, const node & cH )
private

Computes recursively the block graph for every block.

Parameters:
 bT is a block node in the BC-tree. cH is a node of bT in the block graph.
 void ogdf::EmbedderMinDepth::embedBlock ( const node & bT )
private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters:
 bT is the tree node treated in this function call.
 void ogdf::EmbedderMinDepth::embedBlock ( const node & bT, const node & cT, ListIterator< adjEntry > & after )
private

Computes the adjacency list for all nodes in a block and calls recursively the function for all blocks incident to nodes in bT.

Parameters:
 bT is the tree node treated in this function call. cT is the parent cut vertex node of bT in the BC-tree. cT is 0 if bT is the root block. after is the adjacency entry of the cut vertex, after which bT has to be inserted.
 void ogdf::EmbedderMinDepth::topDownTraversal ( const node & bT )
private

Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node bT is calculated and before calling the function recursively for all children of bT in the BC-tree, the nodeLength of the cut-vertex which bT and the child have in common is computed. The length of each node is set to 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to 1 if it is in M2 with m2 = $$\max_{v \in V_B, v != c} m_B(v)$$ and M2 = $${c \in V_B \ {v} | m_B(c) = m2}$$.

Parameters:
 bT is a block vertex in the BC-tree.

## Member Data Documentation

 NodeArray ogdf::EmbedderMinDepth::blockG
private

all blocks

Definition at line 137 of file EmbedderMinDepth.h.

 NodeArray< EdgeArray > ogdf::EmbedderMinDepth::eBlockEmbedding_to_eH
private

a mapping of edges in blockG to the auxiliaryGraph of the BC-tree

Definition at line 149 of file EmbedderMinDepth.h.

 NodeArray< EdgeArray > ogdf::EmbedderMinDepth::eH_to_eBlockEmbedding
private

a mapping of edges in the auxiliaryGraph of the BC-tree to blockG

Definition at line 143 of file EmbedderMinDepth.h.

 NodeArray< List > ogdf::EmbedderMinDepth::M2
private

M2 is empty, if |M_B| != 1, otherwise M_B = {cH} M2 = $${cH' \in V_B \ {v} | m_B(cH') = m2}$$ with m2 = $$\max_{vH \in V_B, vH != cH} m_B(vH)$$.

Definition at line 171 of file EmbedderMinDepth.h.

 NodeArray< List > ogdf::EmbedderMinDepth::M_B
private

M_B = $${cH \in B | m_B(cH) = m_B}$$ with m_B = $$\max_{c \in B} m_B(c)$$ and m_B(c) = $$\max {0} \cup {m_{c, B'} | c \in B', B' \neq B}$$.

Definition at line 164 of file EmbedderMinDepth.h.

 EdgeArray ogdf::EmbedderMinDepth::m_cB
private

an array saving the length for each edge in the BC-tree

Definition at line 158 of file EmbedderMinDepth.h.

 NodeArray ogdf::EmbedderMinDepth::minDepth
private

an array containing the minimum depth of each block

Definition at line 155 of file EmbedderMinDepth.h.

 NodeArray< NodeArray > ogdf::EmbedderMinDepth::nBlockEmbedding_to_nH
private

a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree

Definition at line 146 of file EmbedderMinDepth.h.

 NodeArray< List > ogdf::EmbedderMinDepth::newOrder
private

saves for every node of G the new adjacency list

Definition at line 174 of file EmbedderMinDepth.h.

 NodeArray< NodeArray > ogdf::EmbedderMinDepth::nH_to_nBlockEmbedding
private

a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG

Definition at line 140 of file EmbedderMinDepth.h.

 NodeArray< NodeArray > ogdf::EmbedderMinDepth::nodeLength
private

saving for each node in the block graphs its length

Definition at line 152 of file EmbedderMinDepth.h.

private

an adjacency entry on the external face

Definition at line 134 of file EmbedderMinDepth.h.

 BCTree* ogdf::EmbedderMinDepth::pBCTree
private

BC-tree of the original graph

Definition at line 131 of file EmbedderMinDepth.h.

 NodeArray ogdf::EmbedderMinDepth::spqrTrees
private

The SPQR-trees of the blocks

Definition at line 181 of file EmbedderMinDepth.h.

 NodeArray ogdf::EmbedderMinDepth::treeNodeTreated
private

treeNodeTreated saves for all block nodes in the BC-tree if it has already been treated or not.

Definition at line 178 of file EmbedderMinDepth.h.

The documentation for this class was generated from the following file: