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: Goto entry point

 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: 12 November 2019 Event End Date: 12 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
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