Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization
Jünger, Michael and Mutzel, Petra
(1996)
Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization.
Published in:
Graph drawing : Symposium on Graph Drawing, GD '95, Passau, Germany, September 20 - 22, 1995 ; proceedings, Lecture notes in computer science. 1027 Springer 1996, pp. 337-348.
Abstract
We present algorithms for the 2-layer straightline crossing minimization problem that are able to compute exact optima. Our computational results lead us to the conclusion that there is no need for heuristics if one layer is fixed, even though the problem is NP-hard, and that for the general problem with two variable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing the results to optimum solutions.
| Download: |
Download (331Kb) | Preview |
|---|---|
| Export as: | |
| Editorial actions: |  View Item (Login required) |
| Item Type: | Proceedings article |
|---|---|
| Citations: | 47 (Google Scholar) | |
| Uncontrolled Keywords: | 2-layered networks automatic graph drawing branch-and-cut crossing minimization crossing number feedback arcset graph drawing linear ordering polyhedral combinatorics |
| Subjects: | |
| Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
| Related URLs: |
| ZAIK Number: | zpr95-203 |
|---|---|
| Depositing User: | Prof. Dr. Michael Jünger |
| Date Deposited: | 27 Jun 2003 00:00 |
| Last Modified: | 19 Dec 2011 09:45 |
| URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/203 |
