de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Combining Graph Labeling and Compaction

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44788

Klau,  Gunnar W.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45092

Mutzel,  Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-35B1-D
Abstract
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.