A Combinatorial Approach to Orthogonal Placement Problems

This article presents the main results of a PhD thesis that deals with two families of NP-hard orthogonal placement problems. We develop a common combinatorial framework for compaction problems in graph drawing and for labeling problems in computational cartography. Compaction problems are concerned with performing the conversion from a dimensionless description of the orthogonal shape of a graph to an area-efficient drawing in the grid. Map labeling is the task of attaching labels to point-features so that the resulting placement is legible. On the basis of new combinatorial formulations for these problems we develop exact algorithms. Extensive computational studies on real-world benchmarks show that our linear programming-based algorithms solve large instances of the placement problems to provable optimality within short computation time. Often, our algorithms are the first exact algorithms for the respective problem variant.