Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 (Tek) 9/26/83; site mako.UUCP
Path: utzoo!linus!decvax!tektronix!orca!mako!glenm
From: glenm@mako.UUCP (Glen McCluskey)
Newsgroups: net.math,net.graphics
Subject: minimizing crossed lines
Message-ID: <362@mako.UUCP>
Date: Mon, 12-Nov-84 18:36:10 EST
Article-I.D.: mako.362
Posted: Mon Nov 12 18:36:10 1984
Date-Received: Tue, 13-Nov-84 06:49:25 EST
Organization: Tektronix, Wilsonville OR
Lines: 16


The crossed line problem is where you have
a network with points (vertices) and lines (edges)
connecting the points.  The problem is to arrange
the points in such a way that the number of
crossed lines, and lines going through points,
is minimized.

I believe that this problem is NP-complete.  Whether
or not this is the case, I am wondering if anyone
knows of a practical method that achieves reasonably
good results in laying out the network.

			Glen McCluskey
			..tektronix!mako!glenm