[Lemon-user] PlanarEmbedding tests

[Balazs Dezso]

Dear Users and Developers,

I have just finished the Boyer-Myrvold planarity checking and embedding 
algorithms and during the testing I used two interesting tools.

1) The first tool is the Brendan D. McKay's nauty program which is a graph 
generator tool. I used the geng application to generate all non-isomorphic 
undirected graphs on n unlabeled nodes. I have tested my implementation on 
each graph with at most 11 nodes, if the graph is planar then the euler 
formula is tested on the generated embedding, else the generated Kuratowski 
subdivison is checked.
http://cs.anu.edu.au/~bdm/nauty/

2) The second tool is web page. The online encyclopedia of integer sequences 
contains the first few numbers of a very large set of sequences:
http://www.research.att.com/~njas/sequences/Seis.html

I used two sequences.
Number of graphs on n unlabeled nodes
http://www.research.att.com/~njas/sequences/A000088
Number of unlabeled planar simple graphs with n nodes
http://www.research.att.com/~njas/sequences/A005470

I used these to check the overall number of planar graphs and nauty tool 
correctness.

I think these tools could help to make correct implementation of the planar 
embedding algorithm and could be useful for other problems too.

Best, Balazs