# 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

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

.

**Follow-Ups**:**Re: What kind of problem is this?***From:*Terry Reedy

**Re: What kind of problem is this?***From:*Paul E. Black

- 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):