Given a convex region P and a set of irregular polygons with associated profits, the Maximum Polygon Packing Problem seeks a non-overlapping packing of a subset of the polygons (without rotations) into P maximizing the profit of the packed polygons. Depending on the size of an instance, we use different algorithmic solutions: integer linear programs for small instances, genetic algorithms for medium-sized instances and a best-fit approach for large instances. For packing rectilinear polygons we provide a dedicated best-fit algorithm.

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G=(V,E) into a planar straight-line circular drawing of G by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is obvious that such a crossing-free circular drawing always exists and we define the circular shifting number shift∘(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift∘(δG)≤K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift∘(δG)≤n−⌊n−2⌋−2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all of the crossings. For this problem, we provide a tight upper bound shift∘(δG)≤⌊n2⌋−1 and present an O(n2)-time algorithm to compute the circular shifting number of almost-planar drawings.

The touring problem aims to find an "interesting" (round) trip of a given length. Here, what is considered interesting depends on the type of the desired route, e.g., a user may be looking for an off-road cycling trip or fast running route.

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016).

Label placement in maps is a very challenging task that is critical for the overall map quality. Most previous work focused on designing and implementing fully automatic solutions, but the resulting visual and aesthetic quality has not reached the same level of sophistication that skilled human cartographers achieve. We investigate a different strategy that combines the strengths of humans and algorithms. In our proposed labeling method, first an initial labeling is computed that has many well-placed labels but is not claiming to be perfect. Instead it serves as a starting point for an expert user who can then interactively and locally modify the labeling where necessary. In an iterative human-in-the-loop process alternating between user modifications and local algorithmic updates and refinements the labeling can be tuned to the user's needs.