## Generate planar graphs

There are some methods around to create planar graphs. One of these is based on the Delaunay triangulation algorithm from which you can derive its dual, a 3 regular planar graph. Tools and libraries that I found around (sage, networkx and others), permits you to save the graph using one of common format to represent the graph itself, specifically: .dot, .graphml, .GEXF, .gpickle and others). One problem that I found is that if I save the graph I loose the planar representation of it.

Since for what I am trying to do, namely demonstrate with pencil and paper that the four color theorem has a simpler demonstration, I need to work directly with the planar representation of the graph.

I decided to implement my own method (based on edge addition to planar graphs. See “John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004.”) to generate an save the graph directly using its planar representation. Get the code here at: https://github.com/stefanutti/maps-coloring-python. The program generates random planar graphs without using graphs library and most importantly without using complex algorithms, as planar embedding or planarity testing

Planar embedding: “A combinatorial embedding of a graph is a clockwise ordering of the neighbors of each vertex. From this information one can define the faces of the embedding”

sage: T = graphs.TetrahedralGraph()
sage: T.faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]})
[[(0, 1), (1, 2), (2, 0)],
[(3, 2), (2, 1), (1, 3)],
[(3, 0), (0, 2), (2, 3)],
[(3, 1), (1, 0), (0, 3)]]

Edge addition can start from a basic graph of four faces (bottom right). In the third last line of this picture I added edges from a graph with 3 faces and 2 vertices (considering the ocean). But as you can deduct from the other pictures I can safely start from a graph with 4 faces and 4 vertices (bottom right).

## Four color theorem: A fast algorithm – 2

https://4coloring.wordpress.com/2016/10/16/four-color-theorem-a-fast-algorithm

These are the OLD and NEW (last column) execution times on my new laptop:

• 100 – 196 vertices, 294 edges = 0 seconds – 0 seconds
• 200 – 396 vertices, 594 edges = 1 seconds – 0 seconds
• 300 – 596 vertices, 894 edges = 4 seconds – 1 second
• 400 – 796 vertices, 1194 edges = 6 seconds – 1 second
• 500 – 996 vertices, 1494 edges = 8 seconds – 2 seconds
• 600 – 1196 vertices, 1794 edges = 10 seconds – 4 seconds
• 700 – 1396 vertices, 2094 edges = 16 seconds – 6 seconds
• 800 – 1596 vertices, 2394 edges = 18 seconds – 7 seconds
• 900 – 1796 vertices, 2694 edges = 22 seconds – 9 seconds
• 1000 – 1996 vertices, 2994 edges = 26 seconds – 11 seconds

## I moved the code under github

I moved all code under github here: https://github.com/stefanutti

• I organized the folders a little betters (different github repos)
• I’m experimenting docker to deliver & deploy the Java and Python software
• I’ll also try to integrate a deep learning module, based on Tensorflow, to help me find the “missing piece”

## Four color theorem: about edges selection

For the decomposition of a graph representing a map, I’m trying to use different algorithms to select the edge to remove.

The question is:

• When you have multiple valid choices, which is the best edge to select … if any?

Some basic rules are:

• Avoid new F5 to be created
• Get rid of F5 whenever is possible, selecting the edge of a face with 2, 3 or 4 edges
• Consider to remove an edge from an F5 face only if no faces with 2, 3, 4 edges exist

Here are all possibilities. Last 2 groups (removing edges from F5 and F6) don’t have to be taken into account. I just wanted to see how it continued after the cases with faces made of 2, 3, 4 and 5 edges:

## Four color theorem: new ideas

This is what I want to try:

• Select an F2, F3  or F4 preferably when it is near an F5 and remove the edge that joins the two faces
• Analyse also the balance of the Euler’s identity when removing edges, to decide if it is better to choose other couple: F2 near the highest or other possibilities
• Let Deepmind DQN (or Tensorflow) learn the best approach for selecting faces and remove the edges
• Controls:
• The selection of the face and the edge based on the characteristics of the neighbor faces
• Scope:
• Avoid the F5 worst case (in the rebuilding phase), when it is necessary to apply the random Kempe’s color switches to solve the impasse

The rule: avoid F5 or at least do not create them.

• Remove F2 when near F5 –> Good (will get rid of the F5 and generate an F3)
• Remove F3 when near F5 –> Good (will get rid of the F5 and generate an F4)
• Remove F4 when near F5 –> NOT Good (will end up with another F5)
• Remove F5 when near F5 –> Good (will get rid of the F5 and generate an F6)

Other to avoid:

• Remove F2 when near F7 –> NOT Good (will end up with another F5)
• Remove F3 when near F6 –> NOT Good (will end up with another F5)

NOTE:

• It is also important to check what appens to f3 and f4
Posted in math | Tagged , | 1 Comment