What kind of problem is this?
 From: "Arash Partow" <partow@xxxxxxxxx>
 Date: 18 May 2005 22:57:25 0700
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
n1 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
.
 FollowUps:
 Re: What kind of problem is this?
 From: Terry Reedy
 Re: What kind of problem is this?
 From: Paul E. Black
 Re: What kind of problem is this?
 Prev by Date: Re: "Tree" Data Structure Access using Google!
 Next by Date: Re: "Tree" Data Structure Access using Google!
 Previous by thread: "Tree" Data Structure Access using Google!
 Next by thread: Re: What kind of problem is this?
 Index(es):
Relevant Pages
