Re: Re: How do I make Combinatorica graphs of publishable quality?

*To*: mathgroup at smc.vnet.net*Subject*: [mg44188] Re: [mg44145] Re: [mg44130] How do I make Combinatorica graphs of publishable quality?*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sat, 25 Oct 2003 06:26:52 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

On Friday, October 24, 2003, at 05:24 PM, Ed Pegg Jr wrote: > Henning Heiberg-Andersen wrote: > >> Hi, >> >> As far as I can see, Combinatorica doesn't provide any >> embedding algorithms for planar graphs; the built-in >> options give line-crossing. >> >> > I'd like that, too. As a hobby, I've made some programs for Graphs, > you can see them in Eric Weisstein's Mathworld packages. > http://library.wolfram.com/infocenter/MathSource/4775/ > > General planar embedding algorithms are v. complicated and I do not know of any Mathematica implementation. However, the second edition of Stan Wagon's book "Mathematica in Action" contains a package "GraphColoring.m" which works with the old (pre Mathematia 4.2) Combinatorica package. This package has a simple function that tries to find planar embeddings, essentially at random. This is th eusage message form the package: FindPlanarEmbedding::usage = "FindPlanarEmbedding[g] tries random embeddings \ to find a planar embedding of g. Only small graphs g should be used, as the \ method is unlikely to succeed except for small graphs."; I used this package for a term, when I was teaching a course on graph theory and in particular on uniform polyhedra. I modified it somewhat and it was able to find nice looking planar embeddings of many polyhedral graphs. If you run it it is advisable to use the function TimeConstrained otherwise it may sometimes take for ever even int eh case of a graph that is known to be planar. Also, I am not sue how compatible the package is wiht the new version of Combinatorica, it may need some re-writing. Andrzej Kozlowski Yokohama, Japan http://www.mimuw.edu.pl/~akoz/