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_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 ([28]) has running time O(| V|2).
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|2).
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.
bool	TUTTE_EMBEDDING(graph G, 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(graph G, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)
		...
void	SPRING_EMBEDDING(graph G, list<node> fixed, node_array<double>& xpos, node_array<double>& ypos, double xleft, double xright, double ybottom, double ytop, int iterations=250)
		...
int	ORTHO_EMBEDDING(graph G, 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.
int	ORTHO_EMBEDDING(graph G, node_array<int>& xpos, node_array<int>& ypos, edge_array<list<int> >& xbends, edge_array<list<int> >& ybends)
		orthogonal embedding with bend minimization (Tamassia).
bool	ORTHO_DRAW(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)
		...
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)
		...