A combinatorial approach to orthogonal placement problems [Elektronische Ressource] / Gunnar Werner Klau

SSAATRIASVRA Combinatorial Approach toOrthogonal Placement ProblemsGunnar Werner KlauUniversit t des SaarlandesSaarbr cken, GermanyIEEVNISNIUSA Combinatorial Approach toOrthogonal Placement ProblemsSSAATRIASVRA Combinatorial Approach toOrthogonal Placement ProblemsGunnar Werner KlauDissertationzur Erlangung des GradesDoktor der Ingenieurwissenschaften (Dr. I ng.)der Naturwissenschaftlich T echnischen Fakult t Ider Universit t des SaarlandesUniversit t des SaarlandesSaarbr cken, GermanyIEEVNISNIUSDatum des Kolloquiums: 3. September 2001Dekan der Naturwissenschaftlich T echnischen Fakult t I:Prof. Dr. Rainer Schulze P illot Z iemenGutachter:Prof. Dr. Petra Mutzel, Technische Universit t Wien, sterr eichProf. Dr. Kurt Mehlhorn, Max Planck I nstitut f r Informatik, Saarbr ckenvShort AbstractWe study two families of NP-hard orthogonal placement problems that arise in the areaof information visualization both from a theoretical and a practical point of view. Thisthesis contains a common combinatorial framework for compaction problems in orthogo-nal graph drawing and for point-feature labeling problems in computational cartography.Compaction problems are concerned with performing the conversion from a dimension-less description of the orthogonal shape of a graph to an area-eYcient drawing in theorthogonal grid with short edges.