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

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/