The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Inactive » comp.soft-sys.math.mathematica

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: [mg5156] Planar Graph Generation
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Robert Pratt

Posts: 56
Registered: 12/7/04
Re: [mg5156] Planar Graph Generation
Posted: Nov 7, 1996 12:43 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

On Wed, 6 Nov 1996, Scott Guthery wrote:

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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.