Combining Graph Labeling and Compaction (Extended Abstract)Klau, Gunnar W. and Mutzel, Petra (1999) Combining Graph Labeling and Compaction (Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999 , pp. 2737(Official URL: http://dx.doi.org/10.1007/3540466487_3). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540466487_3
AbstractCombinations of graph drawing and map labeling problems yield challenging mathematical problems and have direct applications, e. g., in automation engineering. We call graph drawing problems in which subsets of vertices and edges need to be labeled 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 labeling problem instance have yet to be determined and thus create additional degrees of freedom. We concentrate on the Compaction and Labeling (COLA) Problem: Given an orthogonal representation  as produced by algorithms within the topologyshapemetrics paradigm  and some label information, the task is to generate a labeled orthogonal embedding with minimum total edge length. We characterize feasible solutions of the COLA problem extending an existing framework for solving pure compaction problems. Based on the graphtheoretical characterization, we present a branchandcut algorithm which computes optimally labeled orthogonal drawings for given instances of the COLA problem. First 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.
Actions (login required)
