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.)

# Source code of implementation of Shih and Hsu's algorithm

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.

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 ):

• random planar graphs with n nodes and m=2n edges (P)
• random planar graphs with n nodes and m=2n edges plus a K3,3 on six randomly chosen nodes (P+K3,3);
• random planar graphs with n nodes and m=2n edges plus a K5 on five randomly chosen nodes (P+K5);
• maximal planar graphs with n nodes (MP);
• maximal planar graphs on n nodes plus one additional edge between two random nodes that are not connected (MP+e).

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 1
```
To see the program's help, just type
``` meu_prompt> ./sh_planar
```

# Source code of master's dissertation

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.

and ``noweb'' at http://www.eecs.harvard.edu/~nr/noweb/.

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> ./mkdissertation
```
The file "dissertation.ps.gz" is created.

# Bibliography

1
K. Mehlhorn e St. Näher, The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999.