Optimizing over all combinatorial embeddings of a planar graph

Mutzel, Petra; Weiskircher, René

Local TagsRelease HistoryDetailsSummary

Optimizing over all combinatorial embeddings of a planar graph

Mutzel, P., & Weiskircher, R.(1998). Optimizing over all combinatorial embeddings of a planar graph (MPI-I-1998-1-029). Saarbrücken: Max-Planck-Institut für Informatik.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7B66-A Version Permalink: https://hdl.handle.net/21.11116/0000-0001-5839-D

Genre: Report

Files

show Files

hide Files

:

1998-1-029 (Any fulltext), 11KB

View Save

File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-7B68-6

Name:
1998-1-029

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
text/html / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Mutzel, Petra¹, Author
Weiskircher, René¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

Abstract: Optimizng Over All Combinatorial Embeddings of a Planar Graph". 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 embedding. The motivation for studying this problem arises in graph drawing, where the chosen 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 combinatorial embedding. This system of linear inequalities can be constructed recursively using the data structure of SPQR-trees and a new splitting operation. Our computational results on two benchmark sets of graphs are surprising: The number 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 linear objective functions, the resulting integer linear programs could be generated within 600 seconds and solved within two seconds on a Sun Enterprise 10000 using CPLEX.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1998

Publication Status: Issued

Pages: 23 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-1998-1-029
BibTex Citekey: MutzelWeiskircher98

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -