This application was made to simplify search of planar subgraphs.

Start using this program isn't a problem. Just follow few instructions.

First of all, you need to get a copy of program. Don't forget that you need to have JRE 8 or newer version to run this application. If you haven't JRE 8 or newer version you should follow this link.

You need to create file with adjacency matrix of your graph. The format of matrix is like that:

0 1 1 1 0 0 0
1 0 1 0 1 0 1
1 1 0 1 1 1 1
1 0 1 0 1 1 1
0 1 1 1 0 1 0
0 0 1 1 1 0 1
0 1 1 1 0 1 0

To launch this application move to directory with jar-file and file with adjacency matrix and put command in a command line:

java -jar Planarization.jar example

Where example is a file with adjacency matrix.

Because algorithm has few parts, application prints all computation phases.

First action of application is search of hamiltonian cycle. It prints all steps and in the end of search it prints hamiltonian cycle that was found. If graph hasn't hamiltonian cycle application will stop with relevant message!

After finding a hamiltonian cycle application forms matrix of crossing where each element is a rib.

Application search all inner steady sets that is called "Psi".

Looking through pairs of "Psi" sets application finds maximum dicotyledonous subgraph and it prints only first one. After it application removes ribs that are contained in printed maximum dicotyledonous subgraph, remove empty sets and sets that are subsets of other existing sets. New family of sets "Psi" is using to find new maximum dicotyledonous subgraph. This procedure continues before the family of sets "Psi" doesn't become empty.

All printed pairs of maximum dicotyledonous subgraph create set of planar subgraphs.# Graph-planarization-application