JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

[HermannSW]

I wanted to add an indicator at the vertices, where the "next_incident_edge" can be found.
I wanted to use "/parrow" PostScript define, a line and an arc.
It turned out to be harder than thought to get things right, but now it works as it should.
Currently it is a hack, with all the calculations in modified "embedding_demo.2.js".
Later there will be a "/parrow" like definition in "ps.js" that will be easy to use.

Here again is single-face non-embedding from previous posting, with the new (blue) face traversal indicators

K4-e.single_face.enhanced.png

K4-e.single_face.enhanced.png (27.47 KiB) Viewed 2264 times

P.S:
As already said, not nice right now:

Code: Select all

...
    ps.straight_line_drawing(G, coords, [], size, r, [], false);


    function draw_vertex_edge_label(G, v, e, coords, l) {
        var w = opposite(G, v, e);
        var cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2;
        var cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2;
        var deg = Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / Math.PI;
        v = w;
        e = next_incident_edge(G, v, e);
        w = opposite(G, v, e);
        var deg2 = Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]) * 180 / Math.PI;
        console.log("0 0 0 setrgbcolor");
        console.log("12 " + ps.frm(deg) + " (" + l + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
        console.log("0 0 1 setrgbcolor");
        deg2 += da;
        deg -= da;
        console.log("gsave " + ps.frm(ps.scrx(coords[0][v]) + r*Math.cos((deg - 180)/180*Math.PI)) + " " + ps.frm(ps.scry(coords[1][v]) + r * Math.sin((deg - 180)/180*Math.PI)) + " translate 0 0 moveto " + (deg - 180 + da) + " rotate " + r + " 0 lineto stroke grestore");
        console.log("newpath " + ps.frm(ps.scrx(coords[0][v])) + " " + ps.frm(ps.scry(coords[1][v])) + " " + r + " " + ps.frm(deg2) + " " +ps.frm(deg -180) + " arc stroke");
        console.log(ps.frm(2*r) + " 0 0 0 1 " + ps.frm(deg2 - da) + " " + ps.frm(ps.scrx(coords[0][v]) + r*Math.cos(deg2/180*Math.PI)) + " " + ps.frm(ps.scry(coords[1][v]) + r * Math.sin(deg2/180*Math.PI)) + " parrow");
    }

    r = 18;
    last_face = -1;
    cnt = -1;
    pftv = planar_face_traversal_visitor();
    pftv.begin_face = function () {
        last_face += 1;
        cnt = 0;
    };
    pftv.next_vertex_edge = function (v, e) {
        draw_vertex_edge_label(G, v, e, coords, last_face + "_" + String.fromCharCode(97 + cnt));
        cnt += 1;
    };
    planar_face_traversal(G, pftv);

    console.log("0 0 0 setrgbcolor");

    console.log("0 0 (is_embedding=" + is_embedding(G) + ",");
...

[HermannSW]

It took some time, but now I was able to compute the angle each arc is drawn in previous screenshot.
Why was it so difficult?
Because it is not a single formula, but difference building of "180-deg" (because angle deg is from wrong side of edge) and "deg2", and two while loops for getting angle into 0°..359.99° range. Without the while loops at least one of the angles was always outside of the range:

Code: Select all

...
        var t = deg - 180 - deg2;
        while (t < 0) {
            t = t + 360;
        }
        while (t >=360) {
            t = t - 360;
        }
        console.log("0 0 0 setrgbcolor");
        console.log("12 " + ps.frm(deg) + " (" + l + ": " + ps.frm(t) + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
...

As you can see I just appended formatted "t" value to edge label, so that I can see debug output "in place" during dev:

K4-e.single_face.enhanced.debug.png

K4-e.single_face.enhanced.debug.png (39.29 KiB) Viewed 1781 times

So now that I have the angle, the reason why I need it is, that I need to check for too small angle. For too pointed angle start and end of the arc are on wrong sides, and drawing arc needs to be skipped. In addition the line and parrow need to be moved so that they meet at a point, and do not cross each other. That point is dependent of the angle (15° in example) the line and parrow are distant from the real edges.

Computing the minimal angle and doing that computation of line and parrow join point is next. After that will work, the logic needs to be moved into a PostScript define in order not to pollute JavaScript code.


P.S:
These are the two bad cases for pointed angle I talked about (I moved up rightmost vertex a bit; right with "if (t >= 2*da)" guarding arc output):

bad_cases.pointed_angles.png

bad_cases.pointed_angles.png (3.92 KiB) Viewed 1757 times

[HermannSW]

Short interrupt, I have 3Dprinted connectors for paper drinking straws, toothpicks and match sticks and built C60 fullerenes with them.
Here is 92cm high paper drinking straw C60 fullerene, hanging 3m high at ceiling:

C60_92cm.20%.jpg

C60_92cm.20%.jpg (24.67 KiB) Viewed 1579 times

Lately I am printing polygons with small magnets in middle of edges for creating C60 as well:
https://www.printables.com/model/167146 ... s/comments

After 32h(!) of 3Dprint I have 12 complete pentagons, 12 compete hexagons and 8 hexagon tops.
When current 5h print will have finished I will be able to complete C60.
This is the C60 part that I am able to build as of now:



I played with the polygons, and was able to complete a design with 8 hexagons and 12 pentagons I had not seen before:

C36.1.png.50%.jpg

C36.1.png.50%.jpg (24.84 KiB) Viewed 1583 times

One hexagon at bottom, surrounded by 6 pentagons, with 6 hexagon ring on top, then symmetric top like the bottom.

8 hexagons and 12 pentagons fullerene has (8*6+12*5)/3=36 vertices, so it looks like a C36 fullerene.
To be sure it is, I used fulgen.c …
http://users.cecs.anu.edu.au/~bdm/plantri/
… to compute the 15 non-isomorphic C36 fullerenes

Code: Select all

./fullgen 36 code 6 stdout > c36.txt

and just commited and pushed them (after quite some conversions):
https://github.com/Hermann-SW/planar_gr ... 3e1761a404

Then I realized that the only selectable graph embedding demo I have that does not add arrows is 6coloring demo.
I viewed all C36 graphs, starting with C36.15.a and then decrementing.
I searched for embedding with a ring of 6 hexagons and two hexagons completely surrounded by pentagons.
And I found it, it was the 15th fullerene inspected, C36.1.a ...

The 6 hexagon ring is faces 1+2+4+6+8+10. The two isolated hexagons are faces 18 and 19:

C36.1.col.png

C36.1.col.png (27 KiB) Viewed 1583 times

Having found what I constructed among the enumerated 15 non-isomorphic C36 fullerenes confirmed that my construction was good and no cheat.


P.S:
I removed the ring of 6 hexagons, and C24 fullerene resulted:



There is a unique non-isomorphic C24 only:

Code: Select all

pi@pi400-64:~/plantri52 $ ./fullgen 24 code 6 stdout > c24.txt
Time for generating the patches: 0.0 seconds 
Time for case 1 (Jordan-Curve Petrie Path): 0.0 seconds 
Time for case 2 (Dumb-bell): 0.0 seconds 
Time for case 3 (Sandwich): 0.0 seconds 

MAPLIST: number of patches: 16
BBLIST: number of items in list: 3  number of patches: 5

Generated 2 maps on 24 vertices -- reduced to 1 non-isomorphic maps. 

Total generation time: 0.0 seconds 
end of program
pi@pi400-64:~/plantri52 $ 

P.P:S:
Converted and 6colored C24, with hexagon faces 12 and 13:

[HermannSW]

Back to the planar face traversal angle indicators.
I am done with it in JavaScript, what remains is to move the (horrible right now) JavaScript code into a clean and neat PostScript define.

I was able to determine the radius factor for the point where the line and parrow meat at angle t/2, and that factor is "interesting":

angle_point.tex.dvi.pdf.png

angle_point.tex.dvi.pdf.png (10.01 KiB) Viewed 1405 times

I used Latex a lot in 1st half of the 90s, and every few years in between then and now, last 8 months ago:
https://gist.github.com/Hermann-SW/d20a ... 1d05d07833

That was on 32bit Raspberry Pi OS of my Pi400, today I had to install Latex on my 64bit OS with:

Code: Select all

sudo apt install texlive-latex-recommended

This command does display the formula:

Code: Select all

latex angle_point.tex && dvipdf angle_point.dvi && evince angle_point.pdf

The formula is just:

Code: Select all

R =& r \sin(da) \sqrt{\frac{1}{\tan(t)^2}\left(1 + \sqrt{\tan(t)^2 + 1}\right)^2 + 1}

And here you can see that the angle indicators in case "t < 2*da" work nicely — I intentionally created three differently pointed angles.
The biggest factor is 3.44 for edge 0_a into vertex 1, and out via edge 0_b:

K4-e.single_face.enhanced2.debug.png

K4-e.single_face.enhanced2.debug.png (33.98 KiB) Viewed 1405 times

[HermannSW]

Instead of PostScript define, I moved the code to function "ps.vertex_indicator()".
So new "embedding_demo.4.js" using that looks not bloated anymore:
https://github.com/Hermann-SW/planar_gr ... js#L28-L35

Code: Select all

    function draw_vertex_edge_label(G, v, e, coords, l) {
        var w = opposite(G, v, e);
        var deg = r2d(Math.atan2(coords[1][v] - coords[1][w], coords[0][w] - coords[0][v]));
        var cx = (ps.scrx(coords[0][v]) + ps.scrx(coords[0][w])) / 2;
        var cy = (ps.scry(coords[1][v]) + ps.scry(coords[1][w])) / 2;
        console.log("12 " + ps.frm(deg) + " (" + l + ") " + ps.frm(cx) + " " + ps.frm(cy) + " txtdistdeg");
        ps.vertex_indicator(G, v, e, coords, r, da);
    }

Output is similar to that of previous posting, with debug output on edges removed.
All is ported to Python as well, more details in this Python thread posting:
viewtopic.php?p=2010618#p2010618

Then I realized that the only selectable graph embedding demo I have that does not add arrows is 6coloring demo.

Today I enhanced that 6coloring demo in order to allow for (12) pentagon only coloring.
I added soft links

Code: Select all

node.convex_face_straight_line_drawing.pentagons.js -> node.convex_face_straight_line_drawing.6coloring.js

and

Code: Select all

python/python.convex_face_straight_line_drawing.pentagons.py -> python.convex_face_straight_line_drawing.6coloring.py

in order to be able to select pentagon code, without touching existing argument processing.

All is committed and pused, so you can play with it:
https://github.com/Hermann-SW/planar_graph_playground

I had to export the file to execute as "ARGV0" environment variable in rjs and rpy scripts:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ cat rjs
#!/bin/bash
file=$1
shift
export ARGV0=$file
gcc -E -x c -nostdinc $file | grep -v "^#"  | nodejs - $*
pi@pi400-64:~/planar_graph_playground $ 

node.convex_face_straight_line_drawing.6coloring.js does use that information like this:

Code: Select all

var do_pent = process.env.ARGV0.includes("pent");

graphs/C36.1.a viewed with pentagon coloring by this command:

Code: Select all

rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C36.1.a | gv -

looks like this:

C36.1.pentagons.jpg

C36.1.pentagons.jpg (54.41 KiB) Viewed 1265 times

Here the 6-cycle of hexagons 1+2+4+6+8+10 is much easier to spot, as well as isolated hexagons 18 and 19.


I looked at the other C36.x fullerenes and graphs/C36.4.a looked interesting:

C36.4.pentagons.jpg

C36.4.pentagons.jpg (57.84 KiB) Viewed 1265 times

In this fullerene there is a 8-cycle of hexagons, faces 0+2+4+5+7+8+10+11 (0 is the outer face).
I disassembled C60 built from 3Dprinted polygons and built C36.4, and it worked.
I took photos from both sides, the 8.cycle of orange hexagons is easy to spot:

C36.4.both_sides.50%.jpg

C36.4.both_sides.50%.jpg (26.35 KiB) Viewed 1265 times

I was surprised that the fullerene was able to safely stand on a polyhedron edge.

[HermannSW]

As provisional end of C36.x fullerene investigations I created all 15 pentagon colorings. Unlike before, where I did screenshot of "gv" displaying PostScript file, and then manually cutting the output, this time all is done automatically, with this script:

Code: Select all

#!/bin/bash
for((i=1; i<=15; ++i))
do
./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C36.$i.a > /tmp/x.ps
pstopnm /tmp/x.ps
pnmcut -top 92 -bottom 696 /tmp/x001.ppm > /tmp/x.ppm
pnmtopng /tmp/x.ppm > ful.$i.png
echo $f
done

I then used pngs2anim script to create an animated .gif from then 15 created ful.*.png files, here with 0.5fps:
viewtopic.php?p=1773897&hilit=pngs2anim#p1773897



graphs/C36.14.a did stand out, because it has 3 connected pentagon only components (the other have 1 or 2):

ful.14.png

ful.14.png (6.85 KiB) Viewed 1168 times

I assembled C36.14 with the polygons, again it stands safe on a polyhedron edge:

20220613_202816.part.33%.jpg (25.18 KiB) Viewed 1168 times

P.S:
Below small diffs do color pentagons white and hexagons orange, to match colors of 3Dprinted polygons:

orange.png

orange.png (6.77 KiB) Viewed 1128 times

node.convex_face_straight_line_drawing.6coloring.js:

Code: Select all

     if (do_pent) {
+        console.log("1.0 0.66 0.0 setrgbcolor");
+        console.log(' 0 0');
+        console.log(' ' + size + ' 0');
+        console.log(' ' + size + ' ' + size);
+        console.log(' 0 ' + size);
+        console.log('poly fill');
+
         pent = pentagons(G);

ps.py:

Code: Select all

             pent.forEach(function (face) {
-                console.log(".75 setgray");
+                console.log("1 setgray");
                 face.forEach(function (v) {
                     console.log(' ' + frm(scrx(coords[0][v])) + ' ' + frm(scry(coords[1][v])));
                 });
@@ -92,7 +92,7 @@ if (true) {
             });
             if (pent.length !== 12) {
-                exports.fill_outer_face(outer, coords, "0.75 0.75 0.75");
+                exports.fill_outer_face(outer, coords, "1 1 1");
             }

[HermannSW]

Without OpenSCAD debug output and being able to turn/scale 3D view, I would not have reached this state …
Currently pentagon is not regular as it should when folding correctly:

I really need to get this fold check code working.

graphs/C40.a embedding looks normal:

C40.png

C40.png (6.37 KiB) Viewed 1092 times

But building that C40, with two joining 5-rings of hexagons (1+2+4+6+8 and 11+10+14+13+12) with 3Dprinted polygons shows, that the magnets match, but the hexagon sides do not match. So this is an example of "not foldable with matching sides" fullerene:

C40.plygons.png.25%.jpg

C40.plygons.png.25%.jpg (16.91 KiB) Viewed 1092 times

There is a simple reason why this cannot be foldable:
3 hexagons joining with each angle of 120° sum up top 360° full circle.
That means all three hexagons have to stay in the same plane in 3D space.

[HermannSW]

Easier than doing complete folding if possible, it is to determine whether a planar fullerene embedding is not foldable.
A fullerene consists of pentagons and hexagons only, and it is a cubic graph (all vertices have degree 3).
With three faces joining, there is always a pair of faces sharing an edge with same number of vertices.
The dual edge of that edge has same vertex degree for both of its vertices.
Next, however the two faces are folded, there is either a pentagon of hexagon possible on both sides because of symmetry.
So "not_foldable.js" just checks this necessary condition for all edges of dual graph:

Code: Select all

#include "assert.js"
#include "util.js"
#include "fullerenes.js"
#include "undirected_graph.js"

function prev_incident_edge(G, v, e) {
    var j = ind(G, v, e);
    return G.V[v][(G.E[e][j][1] + degree(G, v) - 1) % degree(G, v)];
}

var D;
var sel = (
    (process.argv.length > 2)
    ? process.argv[2]
    : "graphs/C40.a"
);
var L = parse2file(sel);
var G = from_adjacency_list(L);

assert.assert(is_embedding(G));
D = dual_graph(G);
assert.assert(is_embedding(D));
assert.assert(is_embedding(dual_graph(D)));

forall_edges(D, function(e) {
    var v = source(D, e);
    var w = target(D, e);
    if (degree(D, v) === degree(D, w))
    {
        var f = next_incident_edge(D, v, e);
        var g = prev_incident_edge(D, v, e);
        if (degree(D, opposite(D, v, f)) !== degree(D, opposite(D, v, g))) {
            console.log(sel, "not foldable");
            process.exit(0);
        }
    }
});

console.log(sel, "might be foldable");

Running it for all fullerenes stored sofar in graphs directory identified many fullerenes as "not foldable with regular pentagons and hexagons":

Code: Select all

pi@pi400-64:~/planar_graph_playground $ for f in graphs/C*.a
> do
> ./rjs not_foldable.js $f
> done
graphs/C20.a might be foldable
graphs/C24.a not foldable
graphs/C30.a not foldable
graphs/C36.10.a not foldable
graphs/C36.11.a might be foldable
graphs/C36.12.a not foldable
graphs/C36.13.a not foldable
graphs/C36.14.a not foldable
graphs/C36.15.a not foldable
graphs/C36.1.a might be foldable
graphs/C36.2.a not foldable
graphs/C36.3.a not foldable
graphs/C36.4.a not foldable
graphs/C36.5.a not foldable
graphs/C36.6.a not foldable
graphs/C36.7.a not foldable
graphs/C36.8.a not foldable
graphs/C36.9.a not foldable
graphs/C40.a not foldable
graphs/C50.a not foldable
graphs/C60.a might be foldable
graphs/C70.a not foldable
pi@pi400-64:~/planar_graph_playground $ 

So only C20, C36.11, C36.1 and C60 are "foldable with regular pentagons and hexagons" candidates.

We now that C20 is foldabe (it is the dodecahedron consisting of 12 pentagons).
And we know that C60 is foldable ("football" fullerene with 20 hexagons and 12 pentagons).

C36.1 looks as if it is foldable (6-cycle of white/orange hexagons with two isolated hexagons):

C36.1.pentagons.photo.jpg

C36.1.pentagons.photo.jpg (64.77 KiB) Viewed 1022 times

I just built C36.11, and it looks foldable, but that has to be verified (it has 12-cycle of grey/white pentagons):

C36.11.pentagons.photo.png.50%.jpg

C36.11.pentagons.photo.png.50%.jpg (25.84 KiB) Viewed 1022 times

[HermannSW]

New "might.js" does iterate over all graphs stored in "fullgen" output enumerating all non-isomorphic fullerenes with a given number of vertices. And it outputs all "might be foldable" candidates:

Code: Select all

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {
    var F = require('fs').readFileSync(name, 'utf8').split("\n");

    var l = 1;
    var i = 0;
    while (l < F.length-1) {
        var L = [];
        while (F[l] !== "0") {
            var v = F[l].trim().replace(/ +/g, " ").split(" ")
            L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
            l = l + 1;
        }
        i = i + 1;
        var G = from_adjacency_list(L);
        f(G, i);
        l = l + 1;
    }
}

var D;
assert.assert(process.argv.length > 2);
var sel = process.argv[2];

forall_graphs(sel, function (G, i) {

    assert.assert(is_embedding(G));
    D = dual_graph(G);
    assert.assert(is_embedding(D));
    assert.assert(is_embedding(dual_graph(D)));

    var good = true;
    forall_edges(D, function(e) {
        var v = source(D, e);
        var w = target(D, e);
        if (degree(D, v) === degree(D, w))
        {
            var f = next_incident_edge(D, v, e);
            var g = prev_incident_edge(D, v, e);
            if (degree(D, opposite(D, v, f)) !== degree(D, opposite(D, v, g))) {
                good = false;
            }
        }
    });

    if (good) {
        console.log(sel, i, "might be foldable");
    }
});

Bash loop around gives an overview of all candidates, takes more and more time the more vertices:

Peek_2022-06-16_14-47.gif

Peek_2022-06-16_14-47.gif (38.52 KiB) Viewed 977 times

[HermannSW]

Determining the "might be foldable" candidates up to 60 vertices took only 18 seconds.
I did run search up to 100 vertices, and found no further candidate — that search took more than 78 minutes on 64bit OS Pi400:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time ( for((i=60; i<=100; i+=2)); do echo -en "c$i.txt\r"; ./rjs might.js `~/plantri52/fullgen $i code 6 stdout 2>/dev/null > c$i.txt; echo c$i.txt`; done )
c60.txt 936 might be foldable
c100.txt
real	78m30.533s
user	81m58.393s
sys	1m55.847s
pi@pi400-64:~/planar_graph_playground $ 

I mentioned that in case three regular hexagons are joining at a vertex, they need to stay in same plane in 3D because their (120°) angles sum up to 360°.
I wrote search code "full.js" that finds fullerenes with three joining hexagons:

Code: Select all

...
    var good = false;
    forall_vertices(D, function(v) {
        if (degree(D, v) === 6) {
            forall_incident_edges(D, v, function(e) {
                if (6 === degree(D, opposite(D, v, e))) {
                {
                    var f = next_incident_edge(D, v, e);
                    if (6 === degree(D, opposite(D, v, f))) {
                        good = true;
...

Here is full code:

Code: Select all

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {
    var F = require('fs').readFileSync(name, 'utf8').split("\n");

    var l = 1;
    var i = 0;
    while (l < F.length-1) {
        var L = [];
        while (F[l] !== "0") {
            var v = F[l].trim().replace(/ +/g, " ").split(" ")
            L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
            l = l + 1;
        }
        i = i + 1;
        var G = from_adjacency_list(L);
        f(G, i);
        l = l + 1;
    }
}

var D;
assert.assert(process.argv.length > 2);
var sel = process.argv[2];

forall_graphs(sel, function (G, i) {

    assert.assert(is_embedding(G));
    D = dual_graph(G);
    assert.assert(is_embedding(D));
    assert.assert(is_embedding(dual_graph(D)));

    var good = false;
    forall_vertices(D, function(v) {
        if (degree(D, v) === 6) {
            forall_incident_edges(D, v, function(e) {
                var w = opposite(D, v, e);
                if (6 === degree(D, w))
                {
                    var f = next_incident_edge(D, v, e);
                    if (6 === degree(D, opposite(D, v, f))) {
                        good = true;
                    }
                }
            });
        }
    });

    if (good) {
        console.log(sel, i, "three joining hexagons found");
    }
});

It did find a lot of such fullerenes up to 60 vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ time ( for((i=4; i<=60; i+=2)); do echo -en "c$i.txt\r"; rjs full.js `~/plantri52/fullgen $i code 6 stdout 2>/dev/null > c$i.txt; echo c$i.txt`; done > out ) 

real	0m21.175s
user	0m22.259s
sys	0m2.378s
pi@pi400-64:~/planar_graph_playground $ wc --lines out
5731 out
pi@pi400-64:~/planar_graph_playground $

Next I tested whether any of the "might be foldable" graphs is among those found, expecting none, and confirming none:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ grep c20 out | grep " 1 "
pi@pi400-64:~/planar_graph_playground $ grep c36 out | grep " 1 "
pi@pi400-64:~/planar_graph_playground $ grep c36 out | grep " 11 "
pi@pi400-64:~/planar_graph_playground $ grep c38 out | grep " 7 "
pi@pi400-64:~/planar_graph_playground $ grep c40 out | grep " 18 "
pi@pi400-64:~/planar_graph_playground $ grep c40 out | grep " 19 "
pi@pi400-64:~/planar_graph_playground $ grep c42 out | grep " 39 "
pi@pi400-64:~/planar_graph_playground $ grep c44 out | grep " 51 "
pi@pi400-64:~/planar_graph_playground $ grep c44 out | grep " 53 "
pi@pi400-64:~/planar_graph_playground $ grep c50 out | grep "105 "
pi@pi400-64:~/planar_graph_playground $ grep c60 out | grep " 936 "
pi@pi400-64:~/planar_graph_playground $ 

So I extracted smallest fullerene with 3 hexagons joining, C32.2.a:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ head -1 out
c32.txt 2 three joining hexagons found
pi@pi400-64:~/planar_graph_playground $ 

Just as visual confirmation I did pentagons coloring view of that graph, and it has two such joining 3-hexagon groups.
But it is not "foldable" with regular pentagons/hexagons.
A reason is that joining hexagons 9 and 10 have hexagon 8 and pentagon 11 on both sides of joining edge:

C32.2.a.png

C32.2.a.png (6.83 KiB) Viewed 917 times

[HermannSW]

Still no fold code, but 1st time straight line drawing in 3D.

I used "tutte.convex_face_coordinates()" as before to get 2D coordinates for planar convex face straight line drawing:



The outer face has coordinates on unit circle around 2D origin, so length=1, and all inner vertices have length <1.
I used this code to map the 2D coordinates onto unit sphere in 3D, and scale coordinates before OpenSCAD drawing:
https://github.com/Hermann-SW/planar_gr ... js#L70-L79

Code: Select all

forall_vertices(G, function (v) {
    coords[v] = map_3D(coords2D[0][v], coords2D[1][v]);
});


forall_vertices(G, function (v) {
    coords[v] = scale_3D(coords[v], Math.sqrt(n_vertices(G)));
});

straight_line_drawing_3D(G);

The trick is in function "map_3D()":
https://github.com/Hermann-SW/planar_gr ... js#L30-L34

Code: Select all

function map_3D(x, y) {
    var a = Math.atan2(y, x);
    var l = 0.8 * Math.PI * Math.sqrt(length_2D(x, y));
    return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)];
}

The factor of 0.8 and using "Math.sqrt()" have no mathematical reason besides that fullerenes look nice with them:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ rjs node.straight_line_drawing.3D.js graphs/C32.2.a > x.scad && openscad x.scad

I know of no equivalent to Tutte's algorithm for determining 2D coordinates for creating unit sphere 3D coordinates.
But with "map_3D()" I have unit sphere coordinates covering big part of unit sphere.
So an iterative spring simulation iterative method should end in similar state of equilibrium as with Tutte's formula in 2D.

Here you can see executing the command just shown and zooming and 3D rotation OpenSCAD allows for:




This view shows the 3 joining hexagons of graphs/C32.2.a in front, one in center, the other two hexagons left and right below:

C32.2.3D.png

C32.2.3D.png (69.33 KiB) Viewed 804 times

P.S:
The vertices and edges in background are sometimes a bit confusing.
So I added option "white", which adds a white sphere inside the fullerene.
https://github.com/Hermann-SW/planar_gr ... js#L54-L56

Code: Select all

    if (white) {
        console.log("color([1,1,1]) translate([0,0,0]) sphere(", Math.sqrt(n_vertices(G)) - 1, ");");
    }

Viewing with the white sphere inside is much easier, at least for my eyes:

[HermannSW]

I learned how to use OpenSCAD builtin animation and posted about that, with white sphere in fullerene as example:
viewtopic.php?t=336334

Then I realized how to use OpenSCAD as 3D viewer for different scenes, and "see" debug output for the new iterative unit sphere spring embedder I want to program. Details in this posting, here just the selected red vertex auto rotated in front of origin animation (iterating over all 20 vertices of C20 fullerene (dodecahedron)):
viewtopic.php?t=336334#p2013157

Peek_2022-06-20_21-00.gif

Peek_2022-06-20_21-00.gif (249.25 KiB) Viewed 729 times

[HermannSW]

I had the 3D visualization tools and tried to get iterative spring embedder to work.
Problem was that "move vertex to normalized (for ending on unit sphere) center of its neighbors" did nearly no moves.
The factor 0.8 and using Math.sqrt() created something too good.

So I replaced factor 0.8 with 0.9, and removed Math.sqrt() to get a worse start situation, here two views:

C32.2.candidate_before_move.png

C32.2.candidate_before_move.png (60.53 KiB) Viewed 641 times

What I did to get bigger moves was "to move vertex into center of vertices of its three faces, without the vertex itself":
https://github.com/Hermann-SW/planar_gr ... wing.3D.js
These lines compute 3D sum of the 12..15 vertices "around" the three faces of vertex v, and the normalized value (on sphere):

Code: Select all

sum = filled_array(n_vertices(G), 1, [0,0,0]);
nor = filled_array(n_vertices(G), 1, [0,0,0]);

forall_vertices(G, function (v) {
    var visited = filled_array(n_edges(G), 2, false);
    var face = [];
    forall_incident_edges(G, v, function(e) {
        traverse_face(G, visited, v, e, ind(G, v, e), {next_vertex: function (w) {
            if (v !== w) {
                face.push(w);
            }

Code: Select all

        }});
    });
    face.forEach(function (x) {
        sum[v] = add_3D(sum[v], coords[x]);
    });
    nor[v] = norm_3D(sum[v]);
});

This code determines the vertex with largest distance move (largest distance on unit sphere is 2 between north and south pole). The $vpr line rotates so that the not moved vertex V is in front of origin. Then V gets new coordinate:

Code: Select all

V = 0;
forall_vertices(G, function (v) {
    if (dist_3D(nor[V], coords[V]) < dist_3D(nor[v], coords[v])) {
        V = v;
    }
});

console.log("$vpr = [",-rad2deg(Math.acos(coords[V][2])),",0,",
                       -rad2deg(Math.atan2(coords[V][0], coords[V][1])),"];");

coords[V] = nor[V];

Here you can see the maximal possible initial move (0.6462312041926355 distance):

C32.2.candidate_do_move.png

C32.2.candidate_do_move.png (41.02 KiB) Viewed 641 times

[HermannSW]

Today I posted on "OpenSCAD animation" again, with pure NodeJS external animation, and small demo code "wlog.js":
viewtopic.php?p=2014370#p2014370

I had problems to get animation done with "node.straight_line_drawing.js".
So I did same single call to async function "amain()" as in demo code "wlog.js", and then it worked.
I just commited+pushed latest changes:
https://github.com/Hermann-SW/planar_gr ... 199000548d

Need to verify that calculations are correct at all.
I had replaced call of "traverse_face()" with call of more efficient constant time "face_vertices()" (for constant length faces like pentagons and hexagons as for fullerenes).
I did update the up to maximal 15 vertices of a moved vertex' neighbor faces wrt the move, making this a constant time operation as well.

What I saw and this animated .gif shows is, that the new move is "too heavy" — finally al vertices end up in south half of unit sphere which is not what I want:

Peek_2022-06-26_01-14.gif

Peek_2022-06-26_01-14.gif (183.8 KiB) Viewed 542 times

P.S:
I gave animation more time, and finally all vertices are close to south pole:

finally.1.png

finally.1.png (16.64 KiB) Viewed 522 times

[HermannSW]

I used factor 0.8 and Math.sqrt() again to get a better start vertex distribution.
This time vertices kept in north and south half sphere, but completely moved into east half sphere.

I thought again on Tutte's algorithm for determining vertex coordinates for planar convex face straight line drawing.
That worked because the vertex coordinates of outer face are fixed.

So I wanted to fixate as few vertices as possible on unit sphere for avoiding all vertices moving together.
Minimal number of vertices is 4, vertices of tetrahedron.

I created new "floyd_warshall(G)" all pairs shortest path algorithm:
https://en.wikipedia.org/wiki/Floyd%E2% ... #Algorithm
https://github.com/Hermann-SW/planar_gr ... #L449-L471

Code: Select all

function floyd_warshall(G) {
    var dist = filled_array(n_vertices(G), n_vertices(G), Infinity);

    forall_edges(G, function(e) {
        dist[source(G, e)][target(G, e)] = 1;
        dist[target(G, e)][source(G, e)] = 1;
    });
    forall_vertices(G, function(v) {
        dist[v][v] = 0;
    });

Code: Select all

    forall_vertices(G, function(k) {
        forall_vertices(G, function(i) {
            forall_vertices(G, function(j) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            });
        });
    });
    return dist;
}

It is not the most efficient algorithm for sparse graphs like planar graphs for the task, but it is very simple, and can deal with negative cycles (not needed here).

So I wanted vertices of tetrahedron in a given input fullerene, with sum of six "tetrahedron edge" shortest paths being maximal.
And I wanted all vertices to be far, so I searched for such 4-tuples where shortest path lengths are either x or x-1:

Code: Select all

function ok(a,b,c,d,e,f) {
    var m = Math.max(a, b, c, d, e, f);
    return (((m - a) <= 1) && ((m - b) <= 1) && ((m - c) <= 1) &&
            ((m - d) <= 1) && ((m - e) <= 1) && ((m - f) <= 1));
}

https://github.com/Hermann-SW/planar_gr ... js#L25-L47

Code: Select all

var dist = floyd_warshall(G);
var max = 0;
var M = [0,0,0,0];

forall_vertices(G, function(a) {
    forall_vertices_after(G, a, function(b) {
        forall_vertices_after(G, b, function(c) {
            forall_vertices_after(G, c, function(d) {
                if (dist[a][b] + dist[a][c] + dist[a][d] +
                    dist[b][c] + dist[b][d] + dist[c][d] > max) {
                        if (ok(dist[a][b], dist[a][c], dist[a][d],

Code: Select all

                               dist[b][c], dist[b][d], dist[c][d])) {

                        max = dist[a][b] + dist[a][c] + dist[a][d] +
                              dist[b][c] + dist[b][d] + dist[c][d];
                        M = [a, b, c, d];
                    }
                }
            });
        });
    });
});

I had spotted sum as 18 for C20 before, here confirmd:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C20.a 
12 pentagons for graph
0 non-pentagons for graph
vertices: [ 0, 3, 12, 18 ]
max: 18
dists: 3 3 3 3 3 3
pi@pi400-64:~/planar_graph_playground $ 

I ported to Python as well, here for C60:

Code: Select all

pi@pi400-64:~/planar_graph_playground/python $ ./rpy python.tetra.py ../graphs/C60.a 
12 pentagons for graph
20 non-pentagons for graph
vertices: [0, 5, 35, 48]
max: 34
dists: 5 5 6 6 6 6
pi@pi400-64:~/planar_graph_playground/python $ 

I wanted to "see" the vertices in planar embedding, and enhanced (node|python).convex_face_straight_line_drawing.pentagons, allowing to just pass the vertex numbers to be marked. Here with "0 5 35 48" from last example, with shortest path lengths 5 and 6 for the six tetrahedron shortest paths:

Code: Select all

$ ./rpy python.convex_face_straight_line_drawing.pentagons.py ../graphs/C60.a 0 5 35 48 | gv -

C60.tetra.png

C60.tetra.png (37.79 KiB) Viewed 459 times

Here for C20, with all 6 shortest paths between the 4 vertices of length 3 marked blue (with gimp):

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C20.a 
12 pentagons for graph
0 non-pentagons for graph
vertices: [ 0, 3, 12, 18 ]
max: 18
dists: 3 3 3 3 3 3
pi@pi400-64:~/planar_graph_playground $ ./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C20.a 0 3 12 18 | gv -

C20.tetra.png

C20.tetra.png (41.64 KiB) Viewed 459 times

Instead of using 3-dimensional coordinates on unit sphere, my older son proposed to use polar coordinates instead (two angles).
I can see how to solve system of linear equations for one of the 4 faces of the tetrahedron and fixate all shortest path and inner vertices.
I can also see how to do the same for two faces together, and that would move the vertices of shortest path between both tetrahedron faces combined.
Will try out something next.


P.S:
Using gimp "Paths" tool and "Stroke Path" gives nicer "tetrahedron edge" visualization:

Code: Select all

max: 34
dists: 5 5 6 6 6 6

C60.tetra.paths.png

C60.tetra.paths.png (55.94 KiB) Viewed 400 times

[HermannSW]

If the path coloring would be needed for illustration purposes only, gimp would be good enough.
But the paths need to be determined for splitting graph and solving systems of linear equations.

There is a modification "floyd_warshall_path(G)" that allows to determine the shortest path between a pair of vertices:
https://en.wikipedia.org/wiki/Floyd%E2% ... nstruction

That algorithm stores vertices for the paths. For planar graphs I could compute a 5-compaction to determine the intermediate edges in constant time for each edge. But for non-planar graphs with more edges that is not true anymore. Therefore new function "fw_path()" returns array of edges. Intermediate vertices can be easily determined using "opposite()" from start vertex:
https://github.com/Hermann-SW/planar_gr ... #L502-L513

Code: Select all

function fw_path(next, u, v) {
    var path = [];
    if (next[u][v] == -1) {
        return path;
    }
    while (u !== v) {
        var e = next[u][v];
        path.push(e);
        u = opposite(G, u, e);
    }
    return path;
}

New function "floyd_warshall_path()" returns dist as well as next array:
https://github.com/Hermann-SW/planar_gr ... #L473-L500

Code: Select all

...
    return [dist, next];
}

They can be easily split:

Code: Select all

var dist;
var next;
[dist, next] = floyd_warshall_path(G);

"node.convex_face_straight_line_drawing.pentagons.js" is modified to mark passed vertices as well as edges. For this purpose vertices and edges are passed comma-separated:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C20.a
12 pentagons for graph
0 non-pentagons for graph
vertices: 0,3,12,18
max: 18
dists: 3 3 3 3 3 3
edges: 2,3,6,1,20,22,0,19,29,7,9,23,8,27,28,13,14,16
pi@pi400-64:~/planar_graph_playground $

""edges:" output done by:
https://github.com/Hermann-SW/planar_gr ... js#L55-L61

Code: Select all

var edges = [].concat(fw_path(next, M[0], M[1]),
                      fw_path(next, M[0], M[2]),
                      fw_path(next, M[0], M[3]),
                      fw_path(next, M[1], M[2]),
                      fw_path(next, M[1], M[3]),
                      fw_path(next, M[2], M[3]));
console.log("edges:", String(edges));

Now passing both ...

Code: Select all

./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C20.a 0,3,12,18 2,3,6,1,20,22,0,19,29,7,9,23,8,27,28,13,14,16 | gv -

... shows the 6 tetrahedron shortest paths edges bold:

C20.tetra.paths.png

C20.tetra.paths.png (29.82 KiB) Viewed 374 times

And for C60:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C60.a
12 pentagons for graph
20 non-pentagons for graph
vertices: 0,5,35,48
max: 34
dists: 5 5 6 6 6 6
edges: 2,3,6,7,10,1,36,38,40,59,0,34,31,32,78,76,11,13,49,50,61,60,12,68,70,87,88,77,43,42,25,23,24,75
pi@pi400-64:~/planar_graph_playground $ ./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C60.a 0,5,35,48 2,3,6,7,10,1,36,38,40,59,0,34,31,32,78,76,11,13,49,50,61,60,12,68,70,87,88,77,43,42,25,23,24,75 | gv -

C60.tetra.paths.png

C60.tetra.paths.png (37.19 KiB) Viewed 374 times

[HermannSW]

Running node.tetra.js for graphs/C32.2.a shows that edges can be shared by different tetrahedron shortest paths, here edge between faces 10 and 11 for shortest path from vertex surrounded by face 0(the outer face), 2 and 3 and vertex surrounded by 12, 13, 15 to vertex surrounded by 9, 10, 11:

C32.2.tetra.paths.png

C32.2.tetra.paths.png (22.9 KiB) Viewed 307 times

Next, there can be several different shortest paths between two vertices, here between top vertex and vertex surrounded by faces 13, 28, 29:

C20.tetra.paths.0_48.png

C20.tetra.paths.0_48.png (18.87 KiB) Viewed 307 times

It was not clear to me, since floyd_warschal algorithm was an algorithm for directed graphs, whether always the shortest path from a to b has same edges as shortest path from b to a for undirected graph. I created this test script:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ cat n.js 
// Copyright: https://mit-license.org/

#include "assert.js"
#include "util.js"
#include "undirected_graph.js"

function forall_graphs(name, f) {
    var F = require('fs').readFileSync(name, 'utf8').split("\n");

    var l = 1;
    var i = 0;
    while (l < F.length-1) {
        var L = [];
        while (F[l] !== "0") {
            var v = F[l].trim().replace(/ +/g, " ").split(" ")
            L.push([Number(v[4])-1, Number(v[5])-1, Number(v[6])-1]);
            l = l + 1;
        }
        i = i + 1;
        var G = from_adjacency_list(L);
        f(G, i);
        l = l + 1;
    }
}

assert.assert(process.argv.length > 2);

forall_graphs(process.argv[2], function (G, i) {
    console.log(i);

    assert.assert(is_embedding(G));

    var dist;
    var next;
    [dist, next] = floyd_warshall_path(G);

    forall_vertices(G, function(a) {
        forall_vertices_after(G, a, function(b) {
            if (new Set(fw_path(G, next, a, b).concat(fw_path(G, next, b, a))).size !== dist[a][b]) {
                console.log("edges2:", fw_path(G, next, a, b), fw_path(G, next, b, a));
                process.exit(1);
            }
        });
    });
});
pi@pi400-64:~/planar_graph_playground $ 

I applied the algorith to the 8149 non-isomorphic C70 fullerenes, and tested all choose(80, 2) = 70*69/2 = 2415 pairs of vertices (more than 19 million tests in total).
This just iterates over all 8149 graphs, asserts each read adjacency lists being an embedding and determines shortest paths:

Code: Select all

forall_graphs(process.argv[2], function (G, i) {
    console.log(i);

    assert.assert(is_embedding(G));

    var dist;
    var next;
    [dist, next] = floyd_warshall_path(G);

Here for all pairs of vertices a,b it is checked whether shortest pasth from a to b and b to a have same edges.
If not, edges of shortest paths get reported, and algorithm terminates:

Code: Select all

    forall_vertices(G, function(a) {
        forall_vertices_after(G, a, function(b) {
            if (new Set(fw_path(G, next, a, b).concat(fw_path(G, next, b, a))).size !== dist[a][b]) {
                console.log("edges2:", fw_path(G, next, a, b), fw_path(G, next, b, a));
                process.exit(1);
            }
        });
    });
});

Obviously algorithm does not teminate early, and finishes in 1:44min:

c70.8149.all_pairs_paths.bidirectional.png

c70.8149.all_pairs_paths.bidirectional.png (33.43 KiB) Viewed 307 times

[HermannSW]

I started investigating using spherical coordinates for unit sphere:
https://en.wikipedia.org/wiki/Spherical ... ate_system



Instead of 3-dimensional space ℝ³ coordinate for a point on unit sphere, I used 2-dimensional spherical coordinates (not 3-dimensional since radius r=1 for unit sphere).

tutte.js "convex_face_coordinates()" create x/y coordinates for outer face vertices like this:

Code: Select all

        var angle = Math.PI;
        var delta = factor * (2 * Math.PI) / face.length;

        assert.assert(is_embedding(Emb));
        face.forEach(function (v) {
            x[v] = Math.sin(angle);
            y[v] = Math.cos(angle);
            angle -= delta;
        });

I did not want to change that code, so in modified "node.straight_line_drawing.3D.js"

Code: Select all

function map_3D(x, y) {
//    var a = Math.atan2(y, x);
//    var l = 0.9 * Math.PI * length_2D(x, y);
//    return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)];
    var a = Math.asin(x);
    var l = Math.acos(y);
    return [Math.sin(a) * Math.sin(l), Math.cos(a) * Math.sin(l), Math.cos(l)];
}

I used asin() and acos() to undo that and get back azimuthal angle a and polar angle l in radians.
The mapping to 3D coordinates in function "map_3D()" is described as last in "Cartesian coordinates" section:
https://en.wikipedia.org/wiki/Spherical ... oordinates


Depending on whether number of vertices on outer face is odd (pentagon, left) or even (hexagon, right) 1/2 vertices have y=0, all others have y>0:

C30_C60.y=0.png

C30_C60.y=0.png (44.46 KiB) Viewed 177 times

Now investigating options on how to get all outer face coordinates on equator, or at least some below as well.
Reason is that I want to determine Tutte barycentric coordinates based on the 2-angle coordinates two times, once for blue circle and all vertices inside, and once for blue circle and all vertices outside, with blue circle as "outer face" (around two of the 4 tetrahedron shortest path triangles). And finally combine the determined coordinates for complete embedding of the graph onto unit sphere:

C60.two_triangles.png

C60.two_triangles.png (48.36 KiB) Viewed 177 times

[HermannSW]

OK, next step, this is how the cycle around two shortest path triangles will look like from front:

two_triangles.3D.png

two_triangles.3D.png (9.88 KiB) Viewed 113 times

With this commit cycle around two shortest path triangles gets determined, and all inner vertices get marked:
https://github.com/Hermann-SW/planar_gr ... bffb4e823a
Where special case handling is missing for valid cases, an assertion makes sure to abort if needed.

This is new output of enlarged "vertices", the 4 tetrahedron vertices on cycle, and all inner vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C60.a 
12 pentagons for graph
20 non-pentagons for graph
vertices: 0,5,35,48
max: 34
dists: 5 5 6 6 6 6
edges: 2,3,6,7,10,0,34,31,32,78,76,11,13,49,50,61,60,43,42,25,23,24,75
vertices: 0,5,35,48,18,19,20,21,14,13,34,33,32,31,30,29,38
pi@pi400-64:~/planar_graph_playground $ 

Using the last two edges and vertices outputs

Code: Select all

./rjs node.convex_face_straight_line_drawing.pentagons.js graphs/C60.a 0,5,35,48,18,19,20,21,14,13,34,33,32,31,30,29,38 2,3,6,7,10,0,34,31,32,78,76,11,13,49,50,61,60,43,42,25,23,24,75 > x.ps && gv x.ps

results in this wanted output (for debugging):

C60.two_triangles.marked_vertices.png

C60.two_triangles.marked_vertices.png (25.54 KiB) Viewed 113 times

For solving Tutte system of linear equations all vertices on cycle have to be marked.
The vertices on cycle get assigned coordinates determined from 4 tetrahedron vertices coordinates.
All inner vertices coordinates get computed by solving system of linear equations.

With the method how cycle vertices get coordinates, some will be above and some below equator, so all should be fine.

[HermannSW]

Short interrupt in "draw fullerene on unit sphere" efforts.

Yesterday I committed and pushed Raspberry Pi Pico-W (new, with Wifi) Access Point static file webserver:
https://github.com/Hermann-SW/pico-w
Main demo serves planar_graph_playground, the Pico-W is AP with IP address 192.168.4.1:



In graphs directory there are many maximal planar graphs, from maximal planar graph on 10 vertices 10.a to 2 million vertices maximal planar graph 2000000.a. Even small maximal planar graphs do not look nice in convex face straight line planar embedding, here "graphs/50.a":

50.pentagons.png

50.pentagons.png (30.74 KiB) Viewed 48 times

So I built new "node.to_dual.js" tool, that converts an embedding in adjacency list format to same format dual graph.
The main code is this:
https://github.com/Hermann-SW/planar_gr ... js#L16-L37
Parse input file, convert to graph, assert that it is an embedding and then create dual graph.
Later there will be a graph input/output format different from adjacency lists.
So the "write adjacency lists code" is not part of undirected_graph.js yet:

Code: Select all

L = parse2file(sel);
G = from_adjacency_list(L);

assert.assert(is_embedding(G));

D = dual_graph(G);

console.log("[");
var first = true;
forall_vertices(D, function(v) {
    var a = [];

Code: Select all

    forall_incident_edges(D, v, function(e) {
        a.push(opposite(D, v, e));
    });
    if (!first) {
        console.log(",", a);
    } else {
        first = false;
        console.log(a);
    }
});
console.log("]");

I created dual graphs of maximal planar graphs on 10/20/50/100 vertices D10.a/D20.a/D50.a/D100a.
And I had to do a small fix wrt ".pentagons" outer face drawing code.
All this is committed and pushed:
https://github.com/Hermann-SW/planar_gr ... 14f2f9ef90


Dual graph of maximal planar graph on 50 vertices (with 3*50-6=144 vertices) looks quite nice as cubic graph (because all maximal planar faces are triangles):

D50.pentagons.png

D50.pentagons.png (39 KiB) Viewed 48 times