Next: Graph Morphism Algorithms ( Up: Graph Algorithms Previous: Algorithms for Planar Graphs Contents Index

Graph Drawing Algorithms ( graph_draw )

This section gives a summary of the graph drawing algorithms contained in LEDA. Before using them the header file <LEDA/graph/graph_draw.h> has to be included.

int STRAIGHT_LINE_EMBED_MAP(graph& G, node_array<int>& xcoord, node_array<int>& ycoord)

STRAIGHT_LINE_EMBED_MAP takes as argument a graph G representing a planar map. It computes a straight line embedding of G by assigning non-negative integer coordinates (xcoord and ycoord) in the range 0..2(n - 1) to the nodes. STRAIGHT_LINE_EMBED_MAP returns the maximal coordinate. The algorithm ([32]) has running time O(| V|²).

int STRAIGHT_LINE_EMBEDDING(graph& G, node_array<int>& xc, node_array<int>& yc)

STRAIGHT_LINE_EMBEDDING takes as argument a planar graph G and computes a straight line embedding of G by assigning non-negative integer coordinates (xcoord and ycoord) in the range 0..2(n - 1) to the nodes. The algorithm returns the maximal coordinate and has running time O(| V|²).

bool VISIBILITY_REPRESENTATION(graph& G, node_array<double>& x_pos, node_array<double>& y_pos, node_array<double>& x_rad, node_array<double>& y_rad, edge_array<double>& x_sanch, edge_array<double>& y_sanch, edge_array<double>& x_tanch, edge_array<double>& y_tanch)

computes a visibility representation of the graph G, i.e., each node is represented by a horizontal segment (or box) and each edge is represented by a vertical segment.
Precondition G must be planar and has to contain at least three nodes.

bool TUTTE_EMBEDDING(const graph& G, const list<node>& fixed_nodes, node_array<double>& xpos, node_array<double>& ypos)

computes a convex drawing of the graph G if possible. The list fixed_nodes contains nodes with prescribed coordinates already given in xpos and ypos. The computed node positions of the other nodes are stored in xpos and ypos, too. If the operation is successful, true is returned.

void SPRING_EMBEDDING(const graph& G, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)

computes a straight-line spring embedding of G in the given rectangular region. The coordinates of the computed node positions are returned in xpos and ypos.

void SPRING_EMBEDDING(const graph& G, const list<node>& fixed, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)

as above, however, the positions of all nodes in the fixed list is not changed.

void D3_SPRING_EMBEDDING(const graph& G, node_array<double>& xpos, node_array<double>& ypos, node_array<double>& zpos, double xmin, double xmax, double ymin, double ymax, double zmin, double zmax, int iterations=250)

computes a straight-line spring embedding of G in the 3-dimensional space. The coordinates of the computed node positions are returned in xpos, ypos, and zpos.

int ORTHO_EMBEDDING(const graph& G, const node_array<bool>& crossing, const edge_array<int>& maxbends, node_array<int>& xcoord, node_array<int>& ycoord, edge_array<list<int> >& xbends, edge_array<list<int> >& ybends)

Produces an orthogonal (Tamassia) embedding such that each edge e has at most maxbends[e] bends. Returns true if such an embedding exists and false otherwise. Precondition G must be a planar 4-graph.

int ORTHO_EMBEDDING(const graph& G, node_array<int>& xpos, node_array<int>& ypos, edge_array<list<int> >& xbends, edge_array<list<int> >& ybends)

as above, but with unbounded number of edge bends.

bool ORTHO_DRAW(const graph& G0, node_array<double>& xpos, node_array<double>& ypos, node_array<double>& xrad, node_array<double>& yrad, edge_array<list<double> >& xbends, edge_array<list<double> >& ybends, edge_array<double>& xsanch, edge_array<double>& ysanch, edge_array<double>& xtanch, edge_array<double>& ytanch)

computes a orthogonal drawing of an arbitrary planar graph (nodes of degree larger than 4 are allowd) in the so-called Giotto-Model, i.e. high-degree vertices (of degree greater than 4) will be represented by larger rectangles.

bool SP_EMBEDDING(graph& G, node_array<double>& x_coord, node_array<double>& y_coord, node_array<double>& x_radius, node_array<double>& y_radius, edge_array<list<double> >& x_bends, edge_array<list<double> >& y_bends, edge_array<double>& x_sanch, edge_array<double>& y_sanch, edge_array<double>& x_tanch, edge_array<double>& y_tanch)

computes a series-parallel drawing of G.
Precondition G must be a series-parallel graph.

Next: Graph Morphism Algorithms ( Up: Graph Algorithms Previous: Algorithms for Planar Graphs Contents Index

int	STRAIGHT_LINE_EMBED_MAP(graph& G, node_array<int>& xcoord, node_array<int>& ycoord)
		STRAIGHT_LINE_EMBED_MAP takes as argument a graph G representing a planar map. It computes a straight line embedding of G by assigning non-negative integer coordinates (xcoord and ycoord) in the range 0..2(n - 1) to the nodes. STRAIGHT_LINE_EMBED_MAP returns the maximal coordinate. The algorithm ([32]) has running time O(\| V\|²).
int	STRAIGHT_LINE_EMBEDDING(graph& G, node_array<int>& xc, node_array<int>& yc)
		STRAIGHT_LINE_EMBEDDING takes as argument a planar graph G and computes a straight line embedding of G by assigning non-negative integer coordinates (xcoord and ycoord) in the range 0..2(n - 1) to the nodes. The algorithm returns the maximal coordinate and has running time O(\| V\|²).
bool	VISIBILITY_REPRESENTATION(graph& G, node_array<double>& x_pos, node_array<double>& y_pos, node_array<double>& x_rad, node_array<double>& y_rad, edge_array<double>& x_sanch, edge_array<double>& y_sanch, edge_array<double>& x_tanch, edge_array<double>& y_tanch)
		computes a visibility representation of the graph G, i.e., each node is represented by a horizontal segment (or box) and each edge is represented by a vertical segment. Precondition G must be planar and has to contain at least three nodes.
bool	TUTTE_EMBEDDING(const graph& G, const list<node>& fixed_nodes, node_array<double>& xpos, node_array<double>& ypos)
		computes a convex drawing of the graph G if possible. The list fixed_nodes contains nodes with prescribed coordinates already given in xpos and ypos. The computed node positions of the other nodes are stored in xpos and ypos, too. If the operation is successful, true is returned.
void	SPRING_EMBEDDING(const graph& G, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)
		computes a straight-line spring embedding of G in the given rectangular region. The coordinates of the computed node positions are returned in xpos and ypos.
void	SPRING_EMBEDDING(const graph& G, const list<node>& fixed, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)
		as above, however, the positions of all nodes in the fixed list is not changed.
void	D3_SPRING_EMBEDDING(const graph& G, node_array<double>& xpos, node_array<double>& ypos, node_array<double>& zpos, double xmin, double xmax, double ymin, double ymax, double zmin, double zmax, int iterations=250)
		computes a straight-line spring embedding of G in the 3-dimensional space. The coordinates of the computed node positions are returned in xpos, ypos, and zpos.
int	ORTHO_EMBEDDING(const graph& G, const node_array<bool>& crossing, const edge_array<int>& maxbends, node_array<int>& xcoord, node_array<int>& ycoord, edge_array<list<int> >& xbends, edge_array<list<int> >& ybends)
		Produces an orthogonal (Tamassia) embedding such that each edge e has at most maxbends[e] bends. Returns true if such an embedding exists and false otherwise. Precondition G must be a planar 4-graph.
int	ORTHO_EMBEDDING(const graph& G, node_array<int>& xpos, node_array<int>& ypos, edge_array<list<int> >& xbends, edge_array<list<int> >& ybends)
		as above, but with unbounded number of edge bends.
bool	ORTHO_DRAW(const graph& G0, node_array<double>& xpos, node_array<double>& ypos, node_array<double>& xrad, node_array<double>& yrad, edge_array<list<double> >& xbends, edge_array<list<double> >& ybends, edge_array<double>& xsanch, edge_array<double>& ysanch, edge_array<double>& xtanch, edge_array<double>& ytanch)
		computes a orthogonal drawing of an arbitrary planar graph (nodes of degree larger than 4 are allowd) in the so-called Giotto-Model, i.e. high-degree vertices (of degree greater than 4) will be represented by larger rectangles.
bool	SP_EMBEDDING(graph& G, node_array<double>& x_coord, node_array<double>& y_coord, node_array<double>& x_radius, node_array<double>& y_radius, edge_array<list<double> >& x_bends, edge_array<list<double> >& y_bends, edge_array<double>& x_sanch, edge_array<double>& y_sanch, edge_array<double>& x_tanch, edge_array<double>& y_tanch)
		computes a series-parallel drawing of G. Precondition G must be a series-parallel graph.