Visibility Representation ( VisibilityRepresentation )

Baseclasses

Definition

The class VisibilityRepresentation represents the visibility representation algorithm by Rosenstiehl and Tarjan [RT86].

This algorithm draws a planar graph G such that each node is represented by a horizontal segment and each edge is represented by a vertical segment, and incidence between nodes and edges translates to intersection of horizontal and vertical segments.

The grid size is at most (2n - 4) x (n - 1) for a graph with n nodes. G must not contain self-loops or multiple edges.

General Information

Algorithm
name	Visibility Representation
long name	Weak Visibility Representation
author	P. Rosenstiehl, R. E. Tarjan

Implementation
author	D. Alberts
date	1996/1997
version

Pre- and Postcondition

precondition	=	{ planar, simple, noselfloops }
postcondition(PRE)	=	{ straight - line, nocrossings }

Exchangeable Modules Instances of type VisibilityRepresentation provide the following module options:

$\bullet$

augmenter
an AugmentationModule option used for planar biconnected augmentation.

guaranteed precondition:	{planar, simple, noselfloops}
required postcondition:	{planar, biconnected, simple, noselfloops}
initial module:	PlanAug

#include < AGD/VisibilityRepresentation.h >

Creation

VisibilityRepresentation

L

creates an instance L of type VisibilityRepresentation.

Operations

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base classes (LayoutModule, GridLayoutModule).

bool	L.check(const graph& G, AgdKey& p)
void	L.call(const graph& G, LayoutInterface& A)
void	L.call_grid(const graph& G, GridLayout& gl)
IRect	L.bounding_box()
void	L.set_mapper(const GridCoordinateMapper& gcm)

Access to Options

bool

L.set_augmenter(AugmentationModule& M)

Implementation

The computation of the layout takes time $\protectO$(n), where n is the number of nodes of the input graph.