What kind of problem is this?
- From: "Arash Partow" <partow@xxxxxxxxx>
- Date: 18 May 2005 22:57:25 -0700
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
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.
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.