2003 | OriginalPaper | Chapter
A Combinatorial Approach to Orthogonal Placement Problems
Author : Gunnar W. Klau
Published in: Operations Research Proceedings 2002
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.