MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mutzel, Petra
Ziegler, Thomas		dblp
dblp
Editor(s):
Kall, Peter
Lüthi, Hans-Jakob		dblp
dblp
BibTeX cite key*:
MutzelZiegler1998
Title, Booktitle
Title*:
The constrained crossing minimization problem: a first approach
Booktitle*:
Operations Research Proceedings 1998
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Zurich, Switzerland
Language:
English
Event Date*
(no longer used):
August 31 - September 3, 1998
Organization:
Event Start Date:
11 December 2023
Event End Date:
11 December 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
125-134
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
3-540-65381-3
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We investigate the {\em constrained crossing minimization problem} for graphs
defined as follows. Given a connected, planar graph $G=(V,E)$, a combinatorial
embedding $\Pi(G)$ of $G$, and a set of pairwise distinct edges
$F\subseteq V\times V$, find a
drawing of $G\cup F$ in the plane such that the combinatorial embedding
$\Pi(G)$ of $G$ is preserved and the number of edge crossings is minimum.

This problem arises in the context of automatic graph drawing. Here, the
so--called planarization method transforms a general graph into a planar graph
and then applies planar graph drawing methods to it.

First we show NP--hardness of this problem. Then we formulate an $|F|$--pairs
shortest walks problem on an extended dual graph, where the number of crossings
between the walks is added to the cost function. We show that this dual problem
is equivalent to our original problem. Our approach to solve the dual problem
is based on polyhedral combinatorics. We investigate an ILP--formulation and
present first computational results using a branch--and--cut algorithm based on
ABACUS.
Keywords:
Crossing Minimization, Graph Drawing, Integer Linear Programming
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{MutzelZiegler1998,
AUTHOR = {Mutzel, Petra and Ziegler, Thomas},
 EDITOR = {Kall, Peter and L{\"u}thi, Hans-Jakob},
 TITLE = {The constrained crossing minimization problem: a first approach},
 BOOKTITLE = {Operations Research Proceedings 1998},
 PUBLISHER = {Springer},
 YEAR = {1999},
 PAGES = {125--134},
 ADDRESS = {Zurich, Switzerland},
 ISBN = {3-540-65381-3},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Thomas Ziegler		Created
02/10/1999 15:32:25
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
07.04.2000 10:02:40
30.03.2000 16:35:52
30.03.2000 16:34:47
30.03.2000 16:33:52
10/02/99 15:32:25