# 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 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