Re: Slightly off-topic - digraph layout algorithms

Ray Dillinger <bear@sonic.net>
Tue, 05 May 2009 09:41:32 -0700

          From comp.compilers
Related articles
Slightly off-topic - digraph layout algorithms sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-04-13)
Re: Slightly off-topic - digraph layout algorithms DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-04-14)
Re: Slightly off-topic - digraph layout algorithms sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-04-16)
Re: Slightly off-topic - digraph layout algorithms sh006d3592@blueyonder.co.uk (Stephen Horne) (2009-05-03)
Re: Slightly off-topic - digraph layout algorithms dj3vande@eskimo.com (2009-05-04)
Re: Slightly off-topic - digraph layout algorithms bear@sonic.net (Ray Dillinger) (2009-05-05)
| List of all articles for this month |
From: Ray Dillinger <bear@sonic.net>
Newsgroups: comp.compilers
Date: Tue, 05 May 2009 09:41:32 -0700
Organization: Organized? Seems unlikely.
References: 09-04-017 09-05-014 09-05-023
Keywords: tools
Posted-Date: 05 May 2009 14:17:37 EDT

dj3vande@eskimo.com wrote:


> In article 09-05-014,
> Stephen Horne <sh006d3592@blueyonder.co.uk> wrote:
>
>>BTW - am I correct in believing that a graph that can be coloured
>>using four or fewer colours can always be drawn (in 2D) with no arcs
>>crossing?
>
> No.
> K(3,3) (two triples of vertices, with each vertex in each triple having
> edges to all three vertices in the other triple) can be colored with 2
> colors, but doesn't have a planar embedding.


Better known as the "utility graph".


Although your proposition was false, the converse property is true.
Any graph that can be laid out in 2d so that no arcs cross, can be
colored with 4 colors so that no two nodes joined by an arc are the
same color.


                                                                Bear
[Well, yeah, that would be the four color map theorem, wouldn't it. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.