MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
Event Address*:
Graz, Austria
Language:
English
Event Date*
(no longer used):
June 9-11
Organization:
Event Start Date:
10 December 2023
Event End Date:
10 December 2023
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
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
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