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):
Kratochvil, Jandblp
BibTeX cite key*:
MZ00
Title, Booktitle
Title*:
The Constrained Crossing Minimization Problem
Booktitle*:
Graph Drawing, Proceedings of the 7th International Symposium (GD-99)
Event, URLs
Conference URL::
http://www.ms.mff.cuni.cz/gd99
Downloading URL:
Event Address*:
Stirin Castle, Czech Republic
Language:
English
Event Date*
(no longer used):
September, 15-19, 1999
Organization:
Event Start Date:
28 September 2023
Event End Date:
28 September 2023
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin, Germany
Type:
Extended Abstract
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1731
Number:
Month:
Pages:
175-185
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
\documentclass[letterpaper]{article}

\begin{document}

\title{The Constrained Crossing Minimization Problem}
\author{Petra Mutzel \and Thomas Ziegler\thanks{Corresponding author,
email: {\tt tziegler@mpi-sb.mpg.de.}
Research supported by ZFE, Siemens AG, M\"unchen.}}
\date{Max-Planck-Institut f\"ur Informatik,\\
Im Stadtwald, D-66123 Saarbr\"ucken}

\maketitle

In this paper we investigate the
{\em constrained crossing minimization problem}
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^\prime=(V,E\cup F)$ such that the
combinatorial embedding $\Pi(G)$ of $G$ is preserved and the number of
crossings is minimized.
The constrained crossing minimization problem arises in the drawing method based on planarization.

The constrained crossing minimization problem is NP--hard.
We can formulate it as an $|F|$--pairs
shortest walks problem on an extended dual graph, in which we want to minimize
the sum of the lengths of the walks plus the number of crossings between walks.

Here we present an integer linear programming formulation (ILP) for the
{\em shortest crossing walks problem}. Furthermore we present
additional valid inequalities that strengthen the formulation. Based on our
results we have designed and implemented a branch and cut algorithm. Our
computational experiments for the constrained crossing minimization problem
on a benchmark set of graphs are encouraging. This is the first time that
practical instances of the problem can be
solved to provable optimality.
\end{document}
Keywords:
crossing minimization, graph drawing, integer linear programming, branch and cut
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{MZ00,
AUTHOR = {Mutzel, Petra and Ziegler, Thomas},
 EDITOR = {Kratochvil, Jan},
 TITLE = {The Constrained Crossing Minimization Problem},
 BOOKTITLE = {Graph Drawing, Proceedings of the 7th International Symposium (GD-99)},
 PUBLISHER = {Springer},
 YEAR = {2000},
 TYPE = {Extended Abstract},
 VOLUME = {1731},
 PAGES = {175--185},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Stirin Castle, Czech Republic},
 ISBN = {0302-9743},
}

Entry last modified by Uwe Brahm, 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
03/23/2000 15:01:11
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Anja Becker
Thomas Ziegler

Edit Dates
05/02/2001 12:02:58 PM
20.03.2001 15:49:45
23/03/2000 15:01:11