viewtopic.php?t=332496

the original plan was to use Boost graph library to do the job.

But for quick prototyping and interaction I did planar_graph_playground for browser with JavaScript and SVG output first.

Can be played with live here:

https://hermann-sw.github.io/planar_graph_playground/

I created several small JavaScript libraries in the repo, the biggest being undirected_graph.js.

Yesterday I posted about small tool rjs to run the library with C includes on the command line with nodejs:

viewtopic.php?t=333272

I updated node_test.js from yesterday to make use of new "print_graph()":

Code: Select all

```
#include "assert.js"
#include "fullerenes.js"
#include "undirected_graph.js"
#include "gauss-jordan.js"
var lookup = [];
var G = from_adjacency_list(F[0]);
assert.assert(is_embedding(G));
console.log("is_embedding(C20) verified, has " + n_faces_planar(G) + " faces");
print_graph(G, "C20: ");
```

This is the output for fullerene graph C20 (dodecahedron):

Code: Select all

```
pi@pi400-64:~/planar_graph_playground $ rjs node_test.js
is_embedding(C20) verified, has 12 faces
C20: 20 vertices, 30 edges
0: (0)9 (1)10 (2)1
1: (2)0 (3)2 (4)15
2: (3)1 (5)14 (6)3
3: (6)2 (7)4 (8)16
4: (7)3 (9)13 (10)5
5: (10)4 (11)6 (12)17
6: (11)5 (13)12 (14)7
7: (14)6 (15)8 (16)18
8: (15)7 (17)11 (18)9
9: (18)8 (0)0 (19)19
10: (1)0 (20)11 (21)14
11: (20)10 (17)8 (22)12
12: (22)11 (13)6 (23)13
13: (23)12 (9)4 (24)14
14: (24)13 (5)2 (21)10
15: (4)1 (25)16 (26)19
16: (25)15 (8)3 (27)17
17: (27)16 (12)5 (28)18
18: (28)17 (16)7 (29)19
19: (29)18 (19)9 (26)15
pi@pi400-64:~/planar_graph_playground $
```

The browser tool I linked to above displays C20 like this: The tool colors all pentagon faces in embedding.

For fullerenes there are always 12 pentagons and "2 + n_edges(G) - n_vertices(G) - 12" hexagons.

So what you see is regular dodecahedron as planar embedding, Wikipedia shows it in 3D:

https://en.wikipedia.org/wiki/Regular_dodecahedron

I made use of "planar face traversal visitor" concept from Boost graph library, just for the naming:

https://www.boost.org/doc/libs/1_79_0/b ... versal.hpp

Instead of defining all functions in a struct, I used JSON object for JavaScript with only defining the functions I want to use. Only cost for that is having to check for undefined before calling:

Code: Select all

```
if (pftv.next_vertex_edge) {
pftv.next_vertex_edge(v, e);
}
```

"dual_graph(G)" is here on github:

https://github.com/Hermann-SW/planar_gr ... #L237-L257

The function turned out to be so simple, now that planar face traversal visitors are used (all JavaScript code in the repo is JSlinted, which forced me to write code the way I did.) I like what JSlint forced me to do with passed planar face traversal visitor functions, but what it requires wrt ternary operators is a bit too line consuming for me, here for auxiliary function:

Code: Select all

```
function ud2st(str) {
return (
(str === undefined)
? ""
: str
);
}
```

last_face is initialized to "undefined" as 0 base number.

e2f is edge to face mapping, with two entries per edge for the different traversal directions, initialized with -1 as "undefined" as well.

"n_planar_faces(G)" returns the number of faces in embedded graph G, and is used to create new graph D with just as many vertices and without edges:

Code: Select all

```
function dual_graph(G) {
var last_face = -1;
var e2f = linear.fill(n_edges(G), 2, -1);
var D = new_graph(n_faces_planar(G));
full_traverse(G, {begin_face: function () {
last_face += 1;
}, next_vertex_edge: function (v, e) {
e2f[e][ind(G, v, e)] = last_face;
}});
```

"ind(G, v, e)" returns index (0 or 1) to be used in e2f array.

For current face traversal the new face number (last_face) gets stored for all edges of the face.

Normally new edge gets created with "new_edge(G, v, w)", but that is no option here since it will not result in an embedding of D.

For the graph representation, for vertex v G.V[v] is array of the edges adjacent to v.

For edge e G.E[e] is array containg of two arrays of 2 elements.

First of the elements in 2-arrays is a vertex, 2nd is index of edge e in that vertex' adjacency list array.

In order to get the control of the ordering in the vertex adjacency lists G.E[e] needs to be initialized as empty array for all edges e:

Code: Select all

```
forall_edges(G, function () {
D.E.push([]);
});
full_traverse(G, {next_vertex_edge: function (v, e) {
new_edge_vertex(D, e2f[e][ind(G, v, e)], e);
}});
return D;
}
```

I created new nodejs test script with C includes for "dual_graph()" testing (by asserting that created dual graph is an embedding as well):

https://github.com/Hermann-SW/planar_gr ... de_dual.js

After including all that is needed, array lookup needs to be initialized as empty array, used in "from_adjacency_list(L)". It uses O(n²) space for graph with n vertices which is not nice for planar graphs which have at most m=3n-6 edges, so linear in number of vertices. This array is needed for perfect hash table for the edges — in "dual_graph()" lookup is not needed since edge e is retrieved from planar face traversal and does not need "to be remembered for 2nd time edge is traversed". Full graph on 5 vertices K5 is not planar, but removing one edge (K5me) makes it planar, and K5me is adjacency list representation of an embedding with vertices in the lists instead of edges in graph representation. Graph G is created from K5me then:

Code: Select all

```
#include "assert.js"
#include "fullerenes.js"
#include "undirected_graph.js"
#include "gauss-jordan.js"
var lookup = [];
var K4 = [[1, 3, 2], [2, 3, 0], [0, 3, 1], [0, 1, 2]];
var K5me = [[1, 2, 3, 4], [2, 0, 4], [4, 3, 0, 1], [4, 0, 2], [1, 0, 3, 2]];
var D;
var G = from_adjacency_list(K5me);
```

First it is asserted that graph G is an embedding, implementation of that function with planar face traversal is so nice:

https://github.com/Hermann-SW/planar_gr ... #L210-L218

Then graph is printed, with name and number of faces additionally:

Code: Select all

```
assert.assert(is_embedding(G));
console.log("is_embedding(K5-e) verified, has " + n_faces_planar(G) + " faces");
print_graph(G, "K5-e: ");
D = dual_graph(G);
assert.assert(is_embedding(D));
console.log("is_embedding(dual_graph(K5-e)) verified, has " + n_faces_planar(D) + " faces");
print_graph(D, "dual_graph(K5-e): ");
```

Finally same output as for graph G is created for dual graph.

And this is execution:

Code: Select all

```
pi@pi400-64:~/planar_graph_playground $ rjs node_dual.js
is_embedding(K5-e) verified, has 6 faces
K5-e: 5 vertices, 9 edges
0: (0)1 (1)2 (2)3 (3)4
1: (4)2 (0)0 (5)4
2: (6)4 (7)3 (1)0 (4)1
3: (8)4 (2)0 (7)2
4: (5)1 (3)0 (8)3 (6)2
is_embedding(dual_graph(K5-e)) verified, has 5 faces
dual_graph(K5-e): 6 vertices, 9 edges
0: (0)1 (5)4 (3)3
1: (0)0 (1)2 (4)4
2: (1)1 (2)3 (7)5
3: (2)2 (3)0 (8)5
4: (4)1 (6)5 (5)0
5: (6)4 (7)2 (8)3
pi@pi400-64:~/planar_graph_playground $
```

planar_graph_playground has htmlsvg.js JavaScript that does the drawing of graph as SVG in browser HTML.

I just started "ps.js", which will do similar output as postscript file.

This will allow to view generated PostScript with a viewer (eg. evince), of just print on printer.

P.S:

In the early 90s as researcher I gave computer science programming courses, and the C code students had to write was required to create PostScript file with the computed results (eg. a random maze). I saw really creative ideas in student homeworks. So back to the (generate postscript) roots ...