# 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

.

## Relevant Pages

• What kind of problem is this?
... the distance between nodes (secondary priority) ... Is it a placement/arrangement thing? ... I see probabilistic algorithms being able to ...
(comp.programming)
• What kind of problem is this?
... the distance between nodes (secondary priority) ... Is it a placement/arrangement thing? ... I see probabilistic algorithms being able to ...
(sci.math.research)
• Re: What kind of problem is this?
... the distance between nodes (secondary priority) ... always shrink the layout and thereby reduce distances. ... I see probabilistic algorithms being able to ...
(comp.theory)
• Re: What kind of problem is this?
... Arash Partow wrote: ... the distance between nodes ... I see probabilistic algorithms being able to ...
(comp.programming)
• Re: What kind of problem is this?
... the distance between nodes (secondary priority) ... I see probabilistic algorithms being able to ... > Sounds an awful lot like VLSI circuit layout to me. ... 'rubber bands' or 'rubber geometry'. ...
(comp.programming)