<p>I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.</p>

<p>A few comments:</p>

<blockquote>
  <ul>
  <li>Number of intersecting edges should be minimal</li>
  </ul>
</blockquote>

<p>Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings). </p>

<p>Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).</p>

<blockquote>
  <ul>
  <li>All edges flow in one direction (i.e from left to right)</li>
  </ul>
</blockquote>

<p>Does it contain cycles? If yes, this is not possible. </p>

<p>A great source for graph drawing algorithms is <a href="http://rads.stackoverflow.com/amzn/click/0133016153" rel="nofollow">Graph Drawing: Algorithms for the Visualization of Graphs</a>.</p>

<p>In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4308636&amp;abstractAccess=no&amp;userType=inst" rel="nofollow">Methods for Visual Understanding of Hierarchical System Structures</a> (chapter 9 in <a href="http://rads.stackoverflow.com/amzn/click/0133016153" rel="nofollow">1</a> describes such methods).</p>

<p>If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).</p>

CC BY-SA 3.0
2011-07-12T13:23:48.623Z
2011-07-12T13:23:48.623Z
George
<ol>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2605" rel="nofollow">TimGA - A Genetic Algorithm for Drawing Undirected Graphs</a> </li>
<li><a href="http://reports-archive.adm.cs.cmu.edu/anon/1998/abstracts/98-189.html" rel="nofollow">A Numerical Optimization Approach to General Graph Drawing</a></li>
</ol>

<p>I was given task similar to yours on my job. I used two things given above. Both the things work and should give you general idea. In the end you will have to do some tweaks that are specific to your graphs. </p>

CC BY-SA 3.0
2011-07-12T13:00:44.043Z
2011-07-12T13:00:44.043Z
Pratik Deoghare
<p>force-based methods are probably the most common for graph visualization but its possible that GAs (more recently investigated for this purpose) are effective &amp; currently underexplored &amp; hybrid GA-force based solutions are possible via force analysis in the fitness function. here are some other refs not cited so far</p>

<ul>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.7377&amp;rep=rep1&amp;type=pdf" rel="nofollow">GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC
CONSTRAINTS</a> Vrajitoru, El-Gamil</p></li>
<li><p><a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=889735" rel="nofollow">Graph layout using a genetic algorithm</a> Barreto, Barbosa</p></li>
<li><p><a href="http://link.springer.com/chapter/10.1007%2F11539902_4" rel="nofollow">Drawing Undirected Graphs with Genetic Algorithms</a> Zhang, Liu, Zhang, Guo</p></li>
</ul>

CC BY-SA 3.0
2015-02-03T17:23:51.967Z
2015-02-03T17:23:51.967Z
vzn
<p>graphviz contains tools to make attractive planar layouts. the papers used to inform the programs are listed at <a href="http://www.graphviz.org/Documentation.php" rel="nofollow">http://www.graphviz.org/Documentation.php</a> .</p>

CC BY-SA 3.0
2015-02-03T04:26:44.250Z
2015-02-03T04:26:44.250Z
Aaron Brick
<p>I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).</p>

<p>I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest</p>

<p><strong>Input:</strong> A graph G = (V,E)<br>
<strong>Output:</strong> A set of assignments, <code>{(xi, yi) for each vi in V}</code>. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.</p>

<p>These are the criteria that I will use to judge a solution (I welcome any suggestions):</p>

<ul>
<li>Number of intersecting edges should be minimal,</li>
<li>All edges flow in one direction (i.e from left to right),</li>
<li>High angular resolution (the smallest angle formed by two edges
incident on the same vertex),</li>
<li>Small area - least important.</li>
</ul>

<p>Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.</p>

<p>My questions are,  </p>

<ul>
<li><p>How wise would it be to go with local search techniques? How likely
would it produce a desired outcome?  </p></li>
<li><p>And what should I start with? Simulated annealing, genetic algorithms
or something else?</p></li>
<li><p>Should I seed randomly at the beginning or use the initial
configuration to start with?</p></li>
<li><p>Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.</p></li>
</ul>

<p>Any help will be greatly appreciated. Thanks.</p>

CC BY-SA 3.0
2011-07-12T13:58:15.143Z
Michele Sebag (http://www.lri.fr/~sebag/), Marc Schoenauer (http://www.lri.fr/~marc/) and Alejandro Rosete-Suarez (from Cuba, I could not find back his webpage) studied how to use genetic algorithms to generate improved representation of graphs, based on user input.
J.y B.y
<optimization><machine-learning><ai.artificial-intel><graph-drawing>
Genetic Algorithm to Draw a Graph? Position assignment problem
Murat
# Genetic Algorithm to Draw a Graph? Position assignment problem

(Asked by: username_0 on 2011-07-12)

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).

I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest

**Input:** A graph G = (V,E)  
**Output:** A set of assignments, `{(xi, yi) for each vi in V}`. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.

These are the criteria that I will use to judge a solution (I welcome any suggestions):

* Number of intersecting edges should be minimal,
* All edges flow in one direction (i.e from left to right),
* High angular resolution (the smallest angle formed by two edges
  incident on the same vertex),
* Small area - least important.

Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.

My questions are,

* How wise would it be to go with local search techniques? How likely
  would it produce a desired outcome?
* And what should I start with? Simulated annealing, genetic algorithms
  or something else?
* Should I seed randomly at the beginning or use the initial
  configuration to start with?
* Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.

Any help will be greatly appreciated. Thanks.

**Tags:** optimization, machine-learning, ai.artificial-intel, graph-drawing
> **Comments:**
> **username_1**: Michele Sebag (http://www.lri.fr/~sebag/), Marc Schoenauer (http://www.lri.fr/~marc/) and Alejandro Rosete-Suarez (from Cuba, I could not find back his webpage) studied how to use genetic algorithms to generate improved representation of graphs, based on user input.  

---

## 4 answers

### Answer by username_2 on 2011-07-12. Score: 3 | Accepted answer

I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.

A few comments:

> * Number of intersecting edges should be minimal

Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings).

Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).

> * All edges flow in one direction (i.e from left to right)

Does it contain cycles? If yes, this is not possible.

A great source for graph drawing algorithms is [Graph Drawing: Algorithms for the Visualization of Graphs](http://rads.stackoverflow.com/amzn/click/0133016153).

In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al [Methods for Visual Understanding of Hierarchical System Structures](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4308636&abstractAccess=no&userType=inst) (chapter 9 in [1](http://rads.stackoverflow.com/amzn/click/0133016153) describes such methods).

If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).


---

### Answer by username_3 on 2011-07-12. Score: 2

1. [TimGA - A Genetic Algorithm for Drawing Undirected Graphs](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2605)
2. [A Numerical Optimization Approach to General Graph Drawing](http://reports-archive.adm.cs.cmu.edu/anon/1998/abstracts/98-189.html)

I was given task similar to yours on my job. I used two things given above. Both the things work and should give you general idea. In the end you will have to do some tweaks that are specific to your graphs.


---

### Answer by username_4 on 2015-02-03. Score: 0

force-based methods are probably the most common for graph visualization but its possible that GAs (more recently investigated for this purpose) are effective & currently underexplored & hybrid GA-force based solutions are possible via force analysis in the fitness function. here are some other refs not cited so far

* [GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC
  CONSTRAINTS](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.7377&rep=rep1&type=pdf) Vrajitoru, El-Gamil
* [Graph layout using a genetic algorithm](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=889735) Barreto, Barbosa
* [Drawing Undirected Graphs with Genetic Algorithms](http://link.springer.com/chapter/10.1007%2F11539902_4) Zhang, Liu, Zhang, Guo


---

### Answer by username_5 on 2015-02-03. Score: 0

graphviz contains tools to make attractive planar layouts. the papers used to inform the programs are listed at <http://www.graphviz.org/Documentation.php> .


---

