Abstract

In this talk we introduce recursive algorithms for generation of three families of plane graphs. These algorithms start with small graphs and iteratively convert them to larger graphs. The families are k-angulations (plane graphs with whose faces are of size k), plane graphs with a given face size sequence and planar hypohamiltonian graphs. Hypohamiltonian graphs have the property that removing each vertex from the graph, there is a Hamiltonian cycle through all remaining vertices while the original graph does not have any such cycle. One of the problems in the literature since 1976 is to find the smallest planar hypohamiltonian graphs. The previous record by Weiner and Araya was a planar graph with 42 vertices. We improve this record by finding 25 planar hypohamiltonian graphs on 40 vertices while discovering many larger ones on 42 and 43 vertices. We also introduce a very fast method for canonical embedding and isomorphism rejection of plane graphs. Most graph generators like plantri generate graphs isomorph-free up to isomorphism of the embedding, however our method does the isomorphism checking up to the underlining graph while taking advantage of the planarity and embeddings to speed up the computation.



Information: