Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: [mg5156] Planar Graph Generation
Posted:
Nov 7, 1996 12:43 AM


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 wellknown. 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 275993250
rpratt@math.unc.edu
On Wed, 6 Nov 1996, Scott Guthery wrote:
> Anybody know a Mathematica technique to generate all finite planar graphs? > > Thanks, Scott > > >



