Pertinent Graphs ( PertinentGraph )

Definition

The class PertinentGraph represents the pertinent graph G(v_$\protectT$) of a node v_$\protectT$ in an SPQR-tree $\protectT$ with original graph G.

The expansion graph E(e) of a virtual skeleton edge e is the skeleton graph of the twin e' of e without e', where each virtual edge e_v again is replaced by its expansion graph E(e_v). The pertinent graph G(v_$\protectT$) of a tree node v_$\protectT$ is obtained from the skeleton S of v_$\protectT$, where each edge except for the reference edge of S is replaced by its expansion graph. Hence, if v_$\protectT$ is not the root node of $\protectT$, all but one edge (and its reversal) in G(v_$\protectT$) correspond to real edges, otherwise all edges correspond to real edges.

The underlying graph, which is returned by get_graph(), represents a map, that is, for each edge (u, v) also the reversal (v, u) exists. If P is the pertinent graph of a PlanarSPQRTree, the underlying graph is a planar map, whose embedding is implied by the embeddings of the skeletons of $\protectT$.

#include < AGD/PertinentGraph.h >

Creation

Pertinent graphs are created by the pertinent_graph() function of SPQRTree.

PertinentGraph

P

creates an empty instance of type PertinentGraph.

Operations

leda_node	P.tree_node()	returns the tree node v$\protectT$ in $\protectT$ whose pertinent graph is P.
leda_graph&	P.get_graph()	returns a reference to G(v$\protectT$).
leda_edge	P.reference_edge()	returns the edge in G(v$\protectT$) that corresponds to the reference edge in skeleton of v$\protectT$ if v$\protectT$ is not the root of $\protectT$, nil otherwise.
leda_edge	P.skeleton_reference_edge()
		returns the reference edge in skeleton of v$\protectT$. Notice that this edge may differ from the current reference edge in skeleton of v$\protectT$ if $\protectT$ has been rerooted after the construction of P.
leda_node	P.original(leda_node v)	returns the vertex in G that corresponds to v. Precondition: v $\in$ G(v$\protectT$)
leda_edge	P.original(leda_edge e)	returns the edge in G that corresponds to e, or nil if e is the reference edge (or its reversal). Precondition: e $\in$ G(v$\protectT$)

Implementation

All operations take constant time. The data structure uses $\protectO$(| G(v_$\protectT$)|) space.