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):

Kall, Peter
Lüthi, Hans-Jakob

dblp
dblp



BibTeX cite key*:

MutzelZiegler1998

Title, Booktitle

Title*:

The constrained crossing minimization problem: a first approach

Booktitle*:

Operations Research Proceedings 1998

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Zurich, Switzerland

Language:

English

Event Date*
(no longer used):

August 31 - September 3, 1998

Organization:


Event Start Date:

17 November 2019

Event End Date:

17 November 2019

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

125-134

Year*:

1999

VG Wort Pages:


ISBN/ISSN:

3-540-65381-3

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We investigate the {\em constrained crossing minimization problem} for graphs
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\cup F$ in the plane such that the combinatorial embedding
$\Pi(G)$ of $G$ is preserved and the number of edge crossings is minimum.

This problem arises in the context of automatic graph drawing. Here, the
so--called planarization method transforms a general graph into a planar graph
and then applies planar graph drawing methods to it.

First we show NP--hardness of this problem. Then we formulate an $|F|$--pairs
shortest walks problem on an extended dual graph, where the number of crossings
between the walks is added to the cost function. We show that this dual problem
is equivalent to our original problem. Our approach to solve the dual problem
is based on polyhedral combinatorics. We investigate an ILP--formulation and
present first computational results using a branch--and--cut algorithm based on
ABACUS.

Keywords:

Crossing Minimization, Graph Drawing, Integer Linear Programming



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{MutzelZiegler1998,
AUTHOR = {Mutzel, Petra and Ziegler, Thomas},
EDITOR = {Kall, Peter and L{\"u}thi, Hans-Jakob},
TITLE = {The constrained crossing minimization problem: a first approach},
BOOKTITLE = {Operations Research Proceedings 1998},
PUBLISHER = {Springer},
YEAR = {1999},
PAGES = {125--134},
ADDRESS = {Zurich, Switzerland},
ISBN = {3-540-65381-3},
}


Entry last modified by Anja Becker, 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
02/10/1999 03:32:25 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
07.04.2000 10:02:40
30.03.2000 16:35:52
30.03.2000 16:34:47
30.03.2000 16:33:52
10/02/99 15:32:25