Number: 387
Title: neato layout failure on simple 6-vertex graph
Submitter: Alexi Savov
Date: Mon Jan 5 21:08:07 2004
Subsys: Neato
Version:
System: x86-Windows-2000 Prof.
Severity: minor
Problem:
I discovered a problem with neato's layout engine when I tried to draw the following simple undirected graph: (see Input below)

Neato draws the following isomorphic graph correctly: 


graph G {
center = 1;
size="10,10";
1;
2;
3;
4;
5;
6;
1 -- 3;
1 -- 4;
1 -- 5;
1 -- 6;
2 -- 4;
2 -- 6;
3 -- 6;
4 -- 5;
4 -- 6;


}

If you could please take a look at this and let me know what you think. Thanks.
Input: 

graph G {
center = 1;
size="10,10";
1;
2;
3;
4;
5;
6;
1 -- 2;
1 -- 4;
2 -- 3;
2 -- 4;
2 -- 5;
3 -- 5;
4 -- 5;
4 -- 6;
5 -- 6;

}
Fix:
I assume the unspecified failure is that the drawing is not planar. This isn't a bug per se, but an artifact of the heuristic nature of the algorithm. In particular, from an initial layout, the solution may get stuck at a local minimum.

We could consider adding some random moves during solution, or other heuristics, in the hope of escaping from local minima.
Owner: erg
Status: Request (6 January 2004)