Planar graph generation

[rlm]

Essentially, this shouldn't be too difficult to implement in Sage:

 http://cs.anu.edu.au/~bdm/papers/plantri-full.pdf

The basic steps to generate plane graphs (graphs embedded in the plane) of minimum degree at least d, connectivity at least k, number of edges at least e, and max face size at most p, are:

1. Implement section 1.3 of the above paper. This allows for a much faster implementation of automorphism group and isomorphism in the case of plane graphs.

2. Generate all planar triangluations, with min degree at least max(d,3), connectivity at least max(k,3). This is described in section 1.2, mainly the third paragraph. Essentially, you start with K_4, and you augment by one of the three moves E_3, E_4, or E_5. The "backwards" step in canonical augmentation here is to first try to remove the least-labeled vertex of degree 3, i.e. try to undo E_3 if possible, or degree 4 if that is possible, i.e. try to undo E_4 if possible, then finally checking for degree 5.

3. Use these, together with edge deletion and canonical augmentation, to generate all plane graphs.

[mvngu]

Add myself since I'm interested in (implementing the ideas of) this ticket.

[ncohen]

Related subject, recently published : Uniform random sampling of planar graphs in linear time

The paper and a Java implementation are available on :  http://algo.inria.fr/fusy/