Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Mutzel, Petra
Ziegler, Thomas

dblp
dblp



Editor(s):

Kratochvil, Jan

dblp



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

URL of the conference:

http://www.ms.mff.cuni.cz/gd99

URL for downloading the paper:


Event Address*:

Stirin Castle, Czech Republic

Language:

English

Event Date*
(no longer used):

September, 15-19, 1999

Organization:


Event Start Date:

13 November 2019

Event End Date:

13 November 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 03:01:11 PM
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