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 ...
    (sci.math.research)
  • 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)
  • 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)