Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Optimizing Over All Combinatorial Embeddings of a Planar Graph

Mutzel, P., & Weiskircher, R. (1999). Optimizing Over All Combinatorial Embeddings of a Planar Graph. In G. Cornuéjols, R. E. Burkard, & G. J. Woeginger (Eds.), Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO-99) (pp. 361-376). Berlin: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35F1-E Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35F3-A
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Mutzel, Petra1, Autor           
Weiskircher, René1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518024
Anderer: Local-ID: C1256428004B93B8-A772937AFE6EAE90C12567B6002E845F-Weiskircher1999
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Graz, Austria
Start-/Enddatum: 1999

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization (IPCO-99)
Genre der Quelle: Konferenzband
 Urheber:
Cornuéjols, Gérard, Herausgeber
Burkard, Rainer E., Herausgeber
Woeginger, Gerhard J., Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 361 - 376 Identifikator: ISBN: 3-540-66019-4

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1610 Artikelnummer: - Start- / Endseite: - Identifikator: -