What kind of problem is this?



Hi all,

The problem is as follows:

1.) You are given a set of n nodes
2.) each node in the set can be connected to as many as
n-1 other nodes in the set


On a 2D plane, layout the nodes in a way such that you
minimize:

1.) the number of edge intersections (priority)
2.) the distance between nodes (secondary priority)



Does anyone know the name or categories of this problem?
Is it a placement/arrangement thing?

Also what kind of algorithms are available, just from the
description, I see probabilistic algorithms being able to
give a good approximate result, are the deterministic
solutions to such problems NP?


Any help would be very much appreciated.



Arash Partow
__________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

.