[Date Index] [Thread Index] [Author Index]

Re: Planar Graph Generation

• To: mathgroup at smc.vnet.net
• Subject: [mg5189] Re: [mg5156] Planar Graph Generation
• From: Robert Pratt <rpratt at math.unc.edu>
• Date: Sat, 9 Nov 1996 02:24:01 -0500
• Sender: owner-wri-mathgroup at wolfram.com

Are you looking for the finite planar graphs on a fixed number n of 
vertices?  Mathematica certainly has the tools, which are contained in 
the standard package DiscreteMath`Combinatorica`.  You can determine 
if two graphs are isomorphic (using IsomorphicQ), whether a graph is 
planar or not (using PlanarQ), and many other graph properties.  
Theoretically, you could generate all graphs on n vertices (including 
many that are isomorphic), keep only one from each isomorphism class, and 
then determine planarity.  Unfortunately, this approach is VERY slow 
unless n is small.  (You are starting out with 2^Binomial[n,2] graphs.)  
If your n is small, the results are already well-known.  Consult Harary's 
classic text (Graph Theory, 1969) for a table of ALL graphs on at most 6 
vertices.  Selecting the planar ones should be straightforward.  If you 
have difficulty with any of them, you can input the graph into 
Mathematica and apply PlanarQ.

Rob Pratt
Department of Mathematics
The University of North Carolina at Chapel Hill
CB# 3250, 331 Phillips Hall
Chapel Hill, NC  27599-3250

rpratt at math.unc.edu

On Wed, 6 Nov 1996, Scott Guthery wrote:

> Anybody know a Mathematica technique to generate all finite planar graphs?
> 
> Thanks, Scott
> 
> 
>