void  complete_graph(graph& G, int n)  
creates a complete graph G with n nodes.  
void  complete_ugraph(graph& G, int n)  
creates a complete undirected graph G with n nodes.  
void  random_graph_noncompact(graph& G, int n, int m)  
generates a random graph with n nodes and m edges. No attempt is made to store all edges in the same adjacency list consecutively. This function is only included for pedagogical reasons.  
void  random_graph(graph& G, int n, int m, bool no_anti_parallel_edges, bool loopfree, bool no_parallel_edges)  
generates a random graph with n
nodes and m
edges.
All edges in the same adjacency list are stored consecutively.
If no_parallel_edges is true then no parallel edges are generated, if loopfree is true then no self loops are generated, and if no_anti_parallel_edges is true then no anti parallel edges are generated. 

void  random_graph(graph& G, int n, int m)  
same as random_graph(G,n,m,false,false,false).  
void  random_simple_graph(graph& G, int n, int m)  
same as random_graph(G,n,m,false,false,true).  
void  random_simple_loopfree_graph(graph& G, int n, int m)  
same as random_graph(G,n,m,false,true,true).  
void  random_simple_undirected_graph(graph& G, int n, int m)  
same as random_graph(G,n,m,true,true,true).  
void  random_graph(graph& G, int n, double p)  
generates a random graph with n nodes. Each edge of the complete graph with n nodes is included with probability p .  
void  test_graph(graph& G)  creates interactively a user defined graph G .  
void  complete_bigraph(graph& G, int a, int b, list< node> & A, list< node> & B)  
creates a complete bipartite graph G with a nodes on side A and b nodes on side B . All edges are directed from A to B .  
void  random_bigraph(graph& G, int a, int b, int m, list< node> & A, list< node> & B, int k = 1)  
creates a random bipartite graph G
with a
nodes on
side A
, b
nodes on side B
, and m
edges. All
edges are directed from A
to B
.
If k > 1 then A and B are divided into k groups of about equal size and the nodes in the i th group of A have their edges to nodes in the i  1 th and i + 1 th group in B . All indices are modulo k . 

void  test_bigraph(graph& G, list< node> & A, list< node> & B)  
creates interactively a user defined bipartite graph G with sides A and B . All edges are directed from A to B .  
void  grid_graph(graph& G, int n)  
creates a grid graph G with n x n nodes.  
void  grid_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
creates a grid graph G of size n x n embedded into the unit square. The embedding is given by xcoord[v] and ycoord[v] for every node v of G .  
void  d3_grid_graph(graph& G, int n)  
creates a threedimensional grid graph G with n x n x n nodes.  
void  d3_grid_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, node_array< double> & zcoord, int n)  
creates a threedimensional grid graph G of size n x n x n embedded into the unit cube. The embedding is given by xcoord[v] , ycoord[v] , and zcoord[v] for every node v of G .  
void  cmdline_graph(graph& G, int argc, char** argv)  
builds graph G
as specified by the command line arguments:

Planar graph: Combinatorial Constructions A maximal planar map with n nodes, n > = 3 , has 3n  6 uedges. It is constructed iteratively. For n = 1 , the graph consists of a single isolated node, for n = 2 , the graph consists of two nodes and one uedge, for n = 3 the graph consists of three nodes and three uedges. For n > 3 , a random maximal planar map with n  1 nodes is constructed first and then an additional node is put into a random face.
The generator with the additional parameter m first generates a maximal planar map and then deletes all but m edges.
The generators with the word map replaced by graph, first generate a map and then delete one edge from each uedge.
void  maximal_planar_map(graph& G, int n)  
creates a maximal planar map G with n nodes.  
void  random_planar_map(graph& G, int n, int m)  
creates a random planar map G with n nodes and m edges.  
void  maximal_planar_graph(graph& G, int n)  
creates a maximal planar graph G with n nodes.  
void  random_planar_graph(graph& G, int n, int m)  
creates a random planar graph G with n nodes and m edges. 
Planar graph: Geometric Constructions
We have two kinds of geometric constructions: triangulations of point sets and intersection graph of line segments. The functions triangulation_map choose points in the unit square and compute a triangulation of them and the functions random_planar_graph construct the intersection graph of segments.
The generators with the word map replaced by graph, first generate a map and then delete one edge from each uedge.
void  triangulation_map(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
chooses n random points in the unit square and returns their triangulation as a plane map in G . The coordinates of node v are returned as xcoord[v] and ycoord[v]. The coordinates are random number of the form x/K where K = 2^{20} and x is a random integer between 0 (inclusive) and K (exclusive).  
void  triangulation_map(graph& G, list< node> & outer_face, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
as above, in addition the list of nodes of the outer face ( convex hull) is returned in outer_face in clockwise order.  
void  triangulation_map(graph& G, int n)  
as above, but only the map is returned.  
void  random_planar_map(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n, int m)  
chooses n random points in the unit square and computes their triangulation as a plane map in G . It then keeps all but m uedges. The coordinates of node v are returned as xcoord[v] and ycoord[v].  
void  triangulation_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
calls triangulation_map and keeps only one of the edges comprising a uedge.  
void  triangulation_graph(graph& G, list< node> & outer_face, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
calls triangulation_map and keeps only one of the edges comprising a uedge.  
void  triangulation_graph(graph& G, int n)  
calls triangulation_map and keeps only one of the edges comprising a uedge.  
void  random_planar_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n, int m)  
calls random_planar_map and keeps only one of the edges comprising a uedge.  
void  triangulated_planar_graph(graph& G, int n)  
old name for triangulation_graph.  
void  triangulated_planar_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
old name for triangulation_graph.  
void  triangulated_planar_graph(graph& G, list< node> & outer_face, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
old name for triangulation_graph.  
void  random_planar_graph(graph& G, node_array< double> & xcoord, node_array< double> & ycoord, int n)  
creates a random planar graph G with n nodes embedded into the unit sqare. The embedding is given by xcoord[v] and ycoord[v] for every node v of G . The generator chooses n segments whose endpoints have random coordinates of the form x/K , where K is the smallest power of two greater or equal to n , and x is a random integer in 0 to K  1 . It then constructs the arrangement defined by the segments and keeps the n nodes with the smallest x coordinates. Finally, it adds edges to make the graph connected.  
void  random_planar_graph(graph& G, int n)  
creates a random planar graph G with n nodes. Uses the preceding function. 
SeriesParallel Graphs
void  random_sp_graph(graph& G, int n, int m)  
creates a random seriesparallel graph G with n nodes and m edges. 