Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Combining Graph Labeling and Compaction

Klau, G. W., & Mutzel, P. (1999). Combining Graph Labeling and Compaction. In J. Kratochvíl (Ed.), Proceedings of the 7th International Symposium on Graph Drawing (GD-99) (pp. 27-37). Berlin: Springer.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Klau, Gunnar W.1, Autor           
Mutzel, Petra1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Combinations of graph drawing and map labeling problems yield challenging mathematical problems and have direct applications, \emph{e.g.}, in automation engineering. We call graph drawing problems in which subsets of vertices and edges need to be labeled \emph{graph labeling problems}. Unlike in map labeling where the position of the objects is specified in the input, the coordinates of vertices and edges in a graph drawing problem instance are yet to be determined and thus create additional degrees of freedom. We concentrate on the \emph{Compaction and Labeling (COLA) Problem}: Given an orthogonal representation---as produced by algorithms within the topology--shape--metrics paradigm---and some label information, the task is to generate a labeled orthogonal embedding with minimum weighted sum of edge length and perimeter. We characterize feasible solutions of the \emph{COLA} problem extending an existing framework for solving pure compaction problems. Based on the graph--theoretical characterization, we present a branch--and--cut algorithm which computes optimally labeled orthogonal drawings for given instances of the \emph{COLA} problem. Computational experiments on a benchmark set of practical instances show that our method is superior to the traditional approach of applying map labeling algorithms to graph drawings. To our knowledge, this is the first algorithm especially designed to solve graph labeling problems.

Details

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

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Stirin Castle, Czech Republic
Start-/Enddatum: 1999

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 7th International Symposium on Graph Drawing (GD-99)
Genre der Quelle: Konferenzband
 Urheber:
Kratochvíl, Jan, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 27 - 37 Identifikator: -

Quelle 2

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