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
Weiskircher, René

dblp
dblp



Editor(s):

Cornuéjols, Gérard
Burkard, Rainer E.
Woeginger, Gerhard J.

dblp
dblp
dblp



BibTeX cite key*:

Weiskircher1999

Title, Booktitle

Title*:

Optimizing Over All Combinatorial Embeddings of a Planar Graph

Booktitle*:

Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO-99)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Graz, Austria

Language:

English

Event Date*
(no longer used):

June 9-11

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:

Lecture Notes in Computer Science

Volume:

1610

Number:


Month:

June

Pages:

361-376

Year*:

1999

VG Wort Pages:


ISBN/ISSN:

3-540-66019-4

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We study the problem of optimizing over the set of all combinatorial embeddings
of a given planar graph.
Our objective function prefers certain cycles of $G$ as face cycles in the embed
ding.
The motivation for studying this problem arises in graph drawing, where the chos
en embedding has an important influence on the aesthetics of the drawing.

We characterize the set of all possible embeddings of a given biconnected planar
graph $G$ by means of a system of linear inequalities with $\{0,1\}$-variables
corresponding to the set of those cycles in $G$ which can appear in a combinator
ial embedding. This system of linear inequalities can be constructed recursively
using SPQR-trees and a new splitting operation.

Our computational results on two benchmark sets of graphs are surprising: The nu
mber of variables
and constraints seems to grow only linearly with the size of the graphs although
the number of
embeddings grows exponentially. For all tested graphs (up to 500 vertices) and l
inear objective
functions, the resulting integer linear programs could be generated within 10 mi
nutes and solved within two seconds on a Sun Enterprise 10000 using CPLEX.

Keywords:

Optimization, Graph Drawing, Integer Linear Programs, SPQR-trees



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{Weiskircher1999,
AUTHOR = {Mutzel, Petra and Weiskircher, Ren{\'e}},
EDITOR = {Cornu{\'e}jols, G{\'e}rard and Burkard, Rainer E. and Woeginger, Gerhard J.},
TITLE = {Optimizing Over All Combinatorial Embeddings of a Planar Graph},
BOOKTITLE = {Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO-99)},
PUBLISHER = {Springer},
YEAR = {1999},
VOLUME = {1610},
PAGES = {361--376},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Graz, Austria},
MONTH = {June},
ISBN = {3-540-66019-4},
}


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)
René Weiskircher
Created
07/22/1999 10:28:05 AM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
30.03.2000 12:27:01
29.03.2000 16:23:59
29.03.2000 16:20:46
29.03.2000 16:20:18
29.03.2000 16:19:35