Planar graph generation

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

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 triangulations, 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.

CC: @nathanncohen @sagetrac-mvngu @slel

Component: graph theory

Keywords: planar graph, triangulation

Issue created by migration from https://trac.sagemath.org/ticket/6074

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:1

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

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/

[fchapoton]

comment:3

Now partially available via plantri spkg : #16970

[slel]

Changed keywords from none to planar graph, triangulation

[slel]

comment:4

Replying to @nathanncohen:

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/

For future reference, Eric Fusy's page is now at: http://www.lix.polytechnique.fr/Labo/Eric.Fusy/

Excerpt of that page about that paper and Java implementation:

Uniform random sampling of planar graphs in linear time.

Random Structures and Algorithms 35(4): 464-522 (2009). pdf

Short version, under the title "Quadratic exact-size and linear approximate-size random generation of planar graphs": Proceedings of the AofA'05 Conference (Analysis of Algorithms-2005), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AD, pp. 125-138 (2005). pdf

Implementation (in java) tar.gz

Regarding plantri, one can now install it as an optional package by running the following in a terminal

sage -i plantri

(not sure if one needs to then run make from the directory where Sage is installed).

[slel]

Description changed:

--- 
+++ 
@@ -6,6 +6,6 @@

 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.
+2. Generate all planar triangulations, 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.