Home News About Us Contact Contributors Disclaimer Help FAQ

 Display Documents

ID: 518058.0, MPI für Informatik / Algorithms and Complexity Group
The Constrained Crossing Minimization Problem
Authors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Graph Drawing, Proceedings of the 7th International Symposium (GD-99)
Start Page:175
End Page:185
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Stirin Castle, Czech Republic
(Start) Date of Conference/Meeting
(YYYY-MM-DD):
2000
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:\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,\\

\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}
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-E40098CB1D416EBDC12568AB004D0340-...
ISSN:0302-9743
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.