de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

The Constrained Crossing Minimization Problem

Mutzel, P., & Ziegler, T. (2000). The Constrained Crossing Minimization Problem. In J. Kratochvil (), Graph Drawing, Proceedings of the 7th International Symposium (GD-99) (pp. 175-185). Berlin, Germany: Springer.

Item is

### Basic

show hide
Bookmark this item:
Genre: Conference Paper

show Files

show

### Creators

show
hide
Creators:
Mutzel, Petra1, Author
Ziegler, Thomas1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

### Content

show
hide
Free keywords: -
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}

### Details

show
hide
Language(s): eng - English
Dates: 2010-03-022000
Pages: -
Publishing info: -
Rev. Method: -
Identifiers: eDoc: 518058
Other: Local-ID: C1256428004B93B8-E40098CB1D416EBDC12568AB004D0340-MZ00
Degree: -

### Event

show
hide
Title: Untitled Event
Place of Event: Stirin Castle, Czech Republic
Start-/End Date: 2000 -

show

### Source 1

show
hide
Title: Graph Drawing, Proceedings of the 7th International Symposium (GD-99)
Source Genre: Proceedings
Creator(s):
Kratochvil, Jan, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 175 - 185 Identifier: -

### Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
Creator(s):
-
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 1731 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743