Algorithms for Series Parallel Graphs

Graphs can be used to represent relational information. This is the reason why it is often useful to draw graphs in order to visualize this relational information.

Example Series Parallel Embedding	A series parallel graph is a graph recursively defined as follows. Base case: A graph G consisting of two nodes s and t connected by an edge is a series parallel graph, s and t are called source and target of G. Let G1 and G2 be two series parallel graphs where s1/t1 are the source/target of G1 and s2/t2 are the source/target of G2. Then the following graphs are also series parallel:
Serial combination: The graph Gs that emerges from identifying t1 with s2. The source of of Gs is s1 and the target of Gs is t2. Parallel combination: The graph Gp that emerges from identifying s1 with s2 and t1 with t2. The source of Gp is s1/s2 and the target is t1/t2.

LEDA Function for Drawing Series Parallel Graphs

SP_EMBEDDING(): Let G=(V,E) be a series parallel graph. SP_EMBEDDING() computes a series parallel embedding of G.

Example SP_EMBEDDING()

See also:

Graph Drawing Algorithms

Algorithms for Planar Graphs

Planar Maps

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms