All of this is part of Alexandre Noma's Masters Dissertation.
Alexandre received support of FAPESP
while doing his Masters degree.
(Esta página em português.)
(Click here for a brief introduction about the planarity testing problem and some related algorithms.)
Recently, Shih and Hsu (SH), and Boyer and Myrvold (BM) described two diferent implementations for Lempel, Even and Cederbaum's algorithm (LEC) to decide if a given graph is planar. The SH and BM algorithms run in linear time on the number of the vertices of the given graph.
We developed an implementation of SH algorithm on the LEDA platform. This implementation was tested on a PC with GNU/Linux and LEDA 4.4.
You must have LEDA and a C++ compiler installed in your system in order to compile the source code.
The latest version of LEDA (for evaluation) is available at http://www.algorithmic-solutions.com/.
Click here for the source code of SH's algorithm (file 'planarity.tar.gz').
To decompress the .tar.gz file in "mydir/", use the following command
my_prompt> tar -zxvpf planarity.tar.gz -C mydir/
After decompressing the file, the directory "mydir/planarity/" is created. The source files of SH's algorithm are in "mydir/planarity/sh-planar/". For BM's algorithm source code, please contact John M. Boyer or go to https://github.com/graph-algorithms/edge-addition-planarity-suite.
In order to compile the programs ``planarity_time'' and ``sh_planar'', execute:
my_prompt> make
planarity_time. This program prints on the standard output
a running time table (in LATEX format)
comparing SH, BM, and the two implementations in the LEDA's library,
which are: one implementation for Hopcroft and Tarjan's algorithm (HT) and one
for Booth and Lueker's algorithm (BL).
(BL is an implementation for LEC, and HT for Auslander, Parter and Goldstein's
algorithm.)
This program tests these algorithms on specific graphs or on random graphs. In random graphs mode, this program uses five kinds of graphs (as described in the LEDA book [1]):
After running "planarity_time", the program prints the following message
Please, type 1 for embedding:Type 1 if you want to include in the running time of each algorithm the time used to calculate a certificate (an embedding if the given graph is planar; a Kuratowski's subgraph otherwise), or just type another value otherwise.
After pressing ENTER, the program prints the following message
Please, specify a graph (gw file) or just press ENTER =Type a file name if you want to run the algorithms on a specific graph, or just hit ENTER if you want the program to run on random graphs.
If no file is given or the specified file is invalid, the following message is printed
Random graphs selected... number of nodes =Type the initial number of vertices for the random graphs.
After pressing ENTER, the program prints the following message
number of lines =Type the number of lines in the table for each kind of graph used in the tests. (For a given kind of graph, a random graph is generated for each line in the table, doubling the number of vertices.)
After pressing ENTER, the program prints the following message
number of graphs per line =Type the number of graphs to be generated at each line in the table. (Each value printed in the table is the average time for the total graphs specified by the user.)
sh_planar. This program helps to debug our implementation of SH.
It can run on random graphs or specific graphs (specified in the
command line).
For instance, the following command tests SH on random graphs with certificate
meu_prompt> ./sh_planar 1To see the program's help, just type
meu_prompt> ./sh_planar
To compile the dissertation, you must have LEDA properly installed in your system (".../LEDA-X.X/Manual/cmd/" must be in the path). You must have also LATEX and the literate programming tool named ``noweb'' properly installed in your system.
The latest version of LEDA (for evaluation) is available at http://www.algorithmic-solutions.com/
and ``noweb'' at http://www.eecs.harvard.edu/~nr/noweb/.
Click here for the dissertation's source code. (file 'dissertation.tar.gz').
To decompress the .tar.gz file in directory ``mydir/'', please type
my_prompt> tar -zxvpf dissertation.tar.gz -C mydir/
After decompressing the .tar.gz file, the directory ``mydir/dissertation/'' is created.
To compile the dissertation, please type
my_prompt> ./mkdissertationThe file "dissertation.ps.gz" is created.