From: "Armand Zohari" <az@invision.de>
To: rusin@math.niu.edu
Date: Sun, 19 Jan 1997 15:17:04 +0100
Subject: optimization problem

Hello Dave,

I got to your homepage as a result of a search at altavista.

I am a programmer with a little mathematical optimization problem.

I have a list of symbols (circles, triangles, etc. of different size ) and a list of
links (each drawn as a pointer) between the symbols.

The problem is to find the optimal position for the symbols (that 
means minimization of the crossing of the links and so on...)

I am programming on PCs.

I thought of using a genetic algorithm, but i did not found a 
good representation of the data yet (how should one implement the
crossing-over-operator) ?

Do you have any idea how I may solve ths problem or who may
help ?

Thanks in advance,

Armand (az@invision.de)

==============================================================================

Date: Sun, 19 Jan 97 17:51:26 CST
From: rusin (Dave Rusin)
To: az@invision.de
Subject: Re:  optimization problem

Your problem has some unusual features if the symbols must be represented
at a fixed size on a page of fixed size -- you might need to jiggle the
positions a little so that the symbols do not overlap. But the principle
question you are asking is well known in graph theory: what is the
minimum number of crossings necessary when representing  a graph.
There is a classic characterization of the curves which may be represented
with no corssings, for example. (It is almost true to say that a graph
can be drawn with no crossings if it contains neither a set of five
mutually connected vertices nor two triples of connected points; you
may be familiar with these as the pentagram and the "that darn utility
connecting puzzle" graph).

I don't keep up with that literature and I certainly don't know what
software is available, but one possible contact is Brendan McKay,
bdm@cs.anu.edu.au (He also has a web page showing some of his work; you
might want to check that this seems close to what you want).

If you find out anything interesting let me know.
dave

==============================================================================

Date: Sun, 19 Jan 97 18:00:20 CST
From: rusin (Dave Rusin)
To: az@invision.de
Subject: Re:  optimization problem

I show add that any graph may be drawn, if not on a plane (or a sphere)
then on a surface with "holes" (a torus, for example); one needs to add
one handle for each unavoidable crossing. Thus your question asks for
the minimum number of holes in the resulting surface. This is called
the _genus_ of the graph. The following citation may be useful
(it's taken from the online version of Math Reviews; paper version vol. 91d)

dave
   
   91d:68054 68Q25 05C10 57M15 68R10
   Thomassen, Carsten(DK-TUD)
   The graph genus problem is NP-complete. (English)
   J. Algorithms 10 (1989), no. 4, 568--576.
   
   For a given graph $G$ and a natural number $k$, determining whether
   $G$ can be embedded on an orientable surface of genus $k$ or less is
   called the graph genus problem. This is one of the few basic problems
   to have remained open for the past 15 years, in that neither a
   polynomial-time algorithm could be found to solve it nor was the
   problem shown to be NP-complete. This paper settles the issue by
   showing that the graph genus problem is indeed NP-complete.
   
   The NP-completeness of the problem is established by showing that the
   independent set problem is polynomially reducible to the graph genus
   problem. As expected, the reduction is achieved through an involved
   series of nonintuitive steps. First, it is shown that if there is a
   set of $t$ independent vertices (pairwise nonadjacent) in the given
   graph $G$ (with $n$ vertices and $q$ edges), then an embedding with
   genus $q-t$ is possible for another graph $G"$, derived from $G$ as
   follows: Each edge $(u,v)$ in $G$ is replaced by a double wheel,
   consisting of a cycle of length $3(n+1)\sp 2$ and a pair of edges
   joining each vertex in this cycle to $u$ and $v$. Furthermore, a new
   vertex $x$ is added to this graph and $x$ is joined to one vertex in
   each of the new cycles. Then it is shown that the resulting graph $G"$
   has genus $q-\alpha(g)$, where $\alpha(G)$ is the independence number
   of $G$. Since $t\leq\alpha(g)$, the graph can also be embedded in a
   surface of genus $q-t$. The primary tool used is the classic Euler
   formula expressing the genus of an embedding in terms of the numbers
   of vertices, edges and faces.
   
   This paper is highly recommended for its important and interesting
   results as well as for its readability. A couple of illustrative
   figures, however, would have enhanced its readability even further.
             Reviewed by Narsingh Deo
   
   Cited in: 96m:05063 94b:05071 
   © Copyright American Mathematical Society 1991, 1997