http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9303
IAI-TR-93-10.ps.pdf:
chapter 8 describes algorithm for creating random maximal planar graphs


GRAPH algorithms
================

make

Should build the program  randomgraph.

The graph file format is that of the LEDA package from the MPI Saarbruecken,
Germany, of Prof. K. Mehlhorn.
The whole ugraph.h package is motivated by that packages datatype
UGRAPH; the difference are plain ANSI-C instead C++, fewer bug ( :-) ) and
more features!

randomgraph
===========

randomgraph                    --> gives short intro
randomgraph 10 -s 12345 -o t.u --> generates random maximal planar graph in
                                   file t.u with random generator seed 12345

Real random graph (seed is epoch time):

$ time ./randomgraph 1000000 -o t.u -s `date +%s`

-------------------------------------
malloc: 18   malloc-free: 0

real	0m3.220s
user	0m3.042s
sys	0m0.176s
s


Only new feature (in case file name ends with ".a"):
write embedding as 0-based adjacency list (for planar_graph_playground)

$ time ./randomgraph 7 -s 1234 -o t.a

-------------------------------------
malloc: 20   malloc-free: 0

real	0m0.002s
user	0m0.002s
sys	0m0.000s
$ cat t.a
[[1,3,5,6,4,2],[0,2,5,3],[0,4,6,5,1],[0,1,5],[0,6,2],[2,6,0,3,1],[5,2,4,0]]
$

"… -o - …" allows to write to stdout; in this case LEDA graph format is written (as if filename would have ".u" suffix).

Have a  lot of fun,

   Hermann Stamm-Wilbrandt.

P.S.: Any comments, bug reports, ... welcome!


Really 1994 code:

$ ls -lst
total 160
 4 -rw-rw-r-- 1 stammw stammw  1080 Jun 21 20:14 LICENSE
 4 -rw-r--r-- 1 stammw stammw   880 Jun 21 20:05 README
 4 -rw-r--r-- 1 stammw stammw  1347 Jun 21 20:00 Makefile
 4 -rw-r--r-- 1 stammw stammw   994 Nov 13  1997 array.h
 4 -rw-r--r-- 1 stammw stammw  1735 Feb 14  1996 basic.h
12 -rw-r--r-- 1 stammw stammw 10593 Feb 10  1996 randomgraph.c
 4 -rw-r--r-- 1 stammw stammw  2724 Dec 17  1994 is_embedding.c
 4 -rw-r--r-- 1 stammw stammw   264 Dec 17  1994 is_embedding.h
16 -rw-r--r-- 1 stammw stammw 12939 Dec 13  1994 list.c
 8 -rw-r--r-- 1 stammw stammw  7330 Dec 13  1994 list.h
 4 -rw-r--r-- 1 stammw stammw  2008 Dec 13  1994 set.c
12 -rw-r--r-- 1 stammw stammw  9297 Dec 13  1994 ugraph.def
40 -rw-r--r-- 1 stammw stammw 36950 Dec 13  1994 ugraph.h
 4 -rw-r--r-- 1 stammw stammw  2147 Nov 28  1994 array.c
 4 -rw-r--r-- 1 stammw stammw  2119 Nov 11  1994 randomgrapho.c
 4 -rw-r--r-- 1 stammw stammw  3807 Sep 13  1994 triangulate.c
 4 -rw-r--r-- 1 stammw stammw   171 Jun 13  1994 randomgrapho.h
 4 -rw-r--r-- 1 stammw stammw    35 Apr 15  1994 triangulate.h
 4 -rw-r--r-- 1 stammw stammw  1517 Apr 15  1994 set.h
 4 -rw-r--r-- 1 stammw stammw  1401 Mar 17  1994 basic.c
 4 -rw-r--r-- 1 stammw stammw  2669 Mar  2  1994 b_urn.h
 4 -rw-r--r-- 1 stammw stammw  1186 Mar  2  1994 b_stack.c
 4 -rw-r--r-- 1 stammw stammw   902 Mar  2  1994 b_stack.h
$