A binary tanglegram is a drawing of a pair S,T of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. par We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an $O(n^3)$-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a $0.878$-approximation.

Metro maps are schematic diagrams of public transport networks that serve as visual aids for route planning and navigation tasks. It is a challenging problem in network visualization to automatically draw appealing metro maps. There are two aspects to this problem that depend on each other: the layout problem of finding station and link coordinates and the labeling problem of placing non-overlapping station labels. par In this paper we present a new integral approach that solves the combined layout and labeling problem (each of which, independently, is known to be NP-hard) using mixed-integer programming (MIP). We identify seven design rules used in most real-world metro maps. We split these rules into hard and soft constraints and translate them into a MIP model. Our MIP formulation finds a metro map that satisfies all hard constraints (if such a drawing exists) and minimizes a weighted sum of costs that correspond to the soft constraints. We have implemented the MIP model and present a case study and the results of an expert assessment to evaluate the performance of our approach in comparison to both manually designed official maps and results of previous layout methods.

Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning---an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. We use a model for consistent dynamic labeling in which a label is represented by a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its active range, corresponding to the scales at which the label will be selected. The active range optimization (ARO) problem is to select active ranges so that no two truncated solids intersect and the sum of the heights of the active ranges is maximized. Simple ARO is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. par Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.

For $t>0$ and $gge 0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is trimmable if for every constant $t>0$, there is a constant $gge 0$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.

Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.

In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in $O(nm)$ time, where $n$ denotes the number of vertices and $m$ the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3, the bounds we achieve are known to be best possible. par We also investigate graphs with block trees of bounded degree, where the $d$-block tree is the adjacency graph of the $d$-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.

For two points $p$ and $q$ in the plane, a straight line~$h$, called a highway, and a real $v>1$, we define the travel time (also known as the city distance) from $p$ and $q$ to be the time needed to traverse a quickest path from $p$ to $q$, where the distance is measured with speed $v$ on $h$ and with speed $1$ in the underlying metric elsewhere. par Given a set $S$ of $n$ points in the plane and a highway speed $v$, we consider the problem of finding a highway that minimizes the maximum travel time over all pairs of points in $S$. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $L_1$- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $O(n^2 log n)$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.

We consider the following packing problem. Let $ be a fixed real in $(0,1]$. We are given a bounding rectangle $ and a set $l R$ of $n$ possibly intersecting unit disks whose centers lie in~$. The task is to pack a set $l B$ of $m$ disjoint disks of radius $ into $ such that no disk in $l B$ intersects a disk in $l R$, where $m$ is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for $alpha = 2/3$. So far only the case of packing squares has been considered. For that case Baur and Fekete have given a polynomial-time algorithm for $2/3$ and have shown that the problem cannot be solved in polynomial time for any $alpha > 13/14$ unless $l P=l NP$.

In this paper we deal with the following natural family of geometric matching problems. Given a class $l C$ of geometric objects and a set $P$ of points in the plane, a $l C$-matching is a set $M subseteq l C$ such that every $C in M$ contains exactly two elements of $P$. The matching is perfect if it covers every point, and strong if the objects do not intersect. We concentrate on matching points using axes-aligned squares and rectangles. We propose an algorithm for strong rectangle matching that, given a set of $n$ points, matches at least $2lfloor n/3 of them, which is worst-case optimal. If we are given a combinatorial matching of the points, we can test efficiently whether it has a realization as a (strong) square matching. The algorithm behind this test can be modified to solve an interesting new point-labeling problem. On the other hand we show that it is NP-hard to decide whether a point set has a perfect strong square matching.

A straight-line drawing $ of a planar graph $G$ need not be plane, but can be made so by untangling it, that is, by moving some of the vertices of $G$. Let shift$(G,$ denote the minimum number of vertices that need to be moved to untangle $. We show that shift$(G,$ is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. par Further we define fix$(G,=n-shift(G,$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $. We give an algorithm that fixes at least $((log n)-1)/log log n$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $n/2$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $G$ of $G$ with fix$(G,G) le n-2+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $H$ of $H$ with fix$(H,H) le 2 n-1+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.

A wireless ad-hoc network can be represented as a graph in which the nodes represent wireless devices, and the links represent pairs of nodes that communicate directly by means of radio signals. The interference caused by a link between two nodes~$u$ and~$v$ can be defined as the number of other nodes that may be disturbed by the signals exchanged by $u$ and~$v$. Given the position of the nodes in the plane, links are to be chosen such that the maximum interference caused by any link is limited and the network fulfills desirable properties such as connectivity, bounded dilation or bounded link diameter. We give efficient algorithms to find the links in two models. In the first model, the signal sent by~$u$ to~$v$ reaches exactly the nodes that are not farther from~$u$ than~$v$ is. In the second model, we assume that the boundary of a signal's reach is not known precisely and that our algorithms should therefore be based on acceptable estimations. The latter model yields faster algorithms.

In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-convex. We are interested in minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably. The problem of decomposing a simple polygon into the least number of convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in $O(n^3)$ time and space, where $n$ is the number of the vertices of the polygon.

Given a set $P$ of $n$ point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating trans- portation network that consists of $c$ non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using $O((c + n) polylog(c + n))$ time and storage by means of a wavefront expansion. For $c in n n)$ our algorithm is faster than an algorithm by Aichholzer et al., which takes $O(n log n + c^2 log c)$ time.

We study the problem of morphing between two polylines that represent linear geographical features like roads or rivers generalized at two different scales. This problem occurs frequently during continuous zooming in interactive maps. Situations in which generalization operators like typification and simplification replace, for example, a series of consecutive bends by fewer bends are not always handled well by traditional morphing algorithms. We attempt to cope with such cases by modeling the problem as an optimal correspondence problem between characteristic parts of each polyline. A dynamic programming algorithm is presented that solves the matching problem in $O(nm)$ time, where $n$ and $m$ are the respective numbers of characteristic parts of the two polylines. In a case study we demonstrate that the algorithm yields good results when being applied to data from mountain roads, a river and a region boundary at various scales.

In geographic information retrieval, queries often utilize names of geographic regions that do not have a well-defined boundary, such as ``Southern France.'' We provide two classes of algorithms for the problem of computing reasonable boundaries of such regions, based on evidence of given data points that are deemed likely to lie either inside or outside the region. Our problem formulation leads to a number of problems related to red-blue point separation and minimum-perimeter polygons, many of which we solve algorithmically. We give experimental results from our implementation and a comparison of the two approaches.

In this paper, we present boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the point sites. Then, we connect each label to its site such that no two connections, so-called leaders, intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. par We consider attaching labels to one, two or all four sides of the rectangle. We investigate rectilinear and straight-line leaders. We present simple and efficient algorithms that minimize the total length of the leaders or, in the case of rectilinear leaders, the total number of bends.

In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph $G$ such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, $s$--$t$ paths, cycles, matchings, and $-factors for $kappa in 1,2$. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of $k^1-varepsilon$ for any $varepsilon > 0$, where $k$ is the number of crossings in $G$. par We then give a simple fixed-parameter algorithm that tests in $O^2^k)$ time whether $G$ has a non-crossing configuration for any of the above, where the $O^-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are $O^1.9999992^k)$ for spanning trees and $O^(3)^k)$ for $s$-$t$ paths and cycles. For spanning trees we also have an $O^1.968^k)$-time Monte-Carlo algorithm. Each $O^$-time decision algorithms can be turned into an $O^(1)^k)$-time optimization algorithm that computes a configuration with the minimum number of crossings.

This paper deals with automating the drawing of subway maps. There are two features of schematic subway maps that make them different from drawings of other networks such as flow charts or organigrams. First, most schematic subway maps use not only horizontal and vertical lines, but also diagonals. This gives more flexibility in the layout process, but it also makes the problem provably hard. Second, a subway map represents a network whose components have geographic locations that are roughly known to the users of such a map. This knowledge must be respected during the search for a clear layout of the network. For the sake of visual clarity the underlying geography may be distorted, but it must not be given up, otherwise map users will be hopelessly confused. In this paper we first give a rather generally accepted list of rules that should be adhered to by a good subway map. Next we survey three recent methods for drawing subway maps, analyze their performance with respect to the above rules, and compare the resulting maps among each other and to official subway maps drawn by graphic designers. We then focus on one of the methods, which is based on mixed-integer linear programming, a widely-used global optimization technique. This method guarantees to find a drawing that fulfills a subset of the above-mentioned rules (if such a drawing exists) and optimizes a weighted sum of costs that correspond to the remaining rules. The method can draw even large subway networks such as the London Underground in an aesthetically pleasing manner, similar to maps made by professional graphic designers. If station labels are included in the optimization process, so far only medium-size networks can be drawn. Finally we give evidence why drawing good subway maps is difficult (even without labels).

Given a set of points in the plane and a constant $tge 1$, a Euclidean $t$-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most~$t$. Such networks have applications in transportation or communication network design and have been studied extensively. par In this paper we study 1-spanners under the Manhattan (or $L_1$-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an $x$- and $y$-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e. Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set $P$ of $n$ points, our algorithm computes in $O(n log n)$ time and linear space a Manhattan network for $P$ whose length is at most 3 times the length of an MMN of $P$. par We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.

In this paper we discuss farthest-point problems in which a set or sequence $S$ of $n$ points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in $O( n)$ time. Our data structure needs $O(n log n)$ space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.

The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the $L_1$-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their $L_1$-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. par We study the following problem: given $n$ non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i)~for arbitrary graphs, the problem is NP-hard; (ii)~for trees, we can solve the problem by linear programming on $O(n^2)$~variables and constraints; (iii)~for paths, we can solve the problem in time~$O(n^3log n)$; (iv)~for rectangles sorted vertically along a path, the problem can be solved in $O(n^2)$ time, and a $(1+$-approximation can be computed in linear time.

Let $P$ be a set of $n$ points in the plane. The geometric minimum-diameter spanning tree (MDST) of $P$ is a tree that spans $P$ and minimizes the Euclidian length of the longest path. It is known that there is always a mono- or a dipolar MDST, i.e. a MDST with one or two nodes of degree greater 1, respectively. The more difficult dipolar case can so far only be solved in slightly subcubic time. par This paper has two aims. First, we present a solution to a new data structure for facility location, the minimum-sum dipolar spanning tree (MSST), that mediates between the minimum-diameter dipolar spanning tree and the discrete two-center problem (2CP) in the following sense: find two centers $p$ and $q$ in $P$ that minimize the sum of their distance plus the distance of any other point (client) to the closer center. This is of interest if the two centers do not only serve their customers (as in the case of the 2CP), but frequently have to exchange goods or personnel between themselves. We give an $O(n^2 log n)$-time algorithm for this problem. A slight modification of our algorithm yields a factor-4/3 approximation of the MDST. par Second, we give two fast approximation schemes for the MDST, i.e. factor-($1+) approximation algorithms. One uses a grid and takes $O^*(E^6-1/3+n)$ time, where $E=1/ and the $O^*$-notation hides terms of type $O(O(1) E)$. The other uses the well-separated pair decomposition and takes $O(n E^3 + E n log n)$ time. A combination of the two approaches runs in $O^*(E^5 + n)$ time. Both schemes can also be applied to MSST and 2CP.

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups; fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. par We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling $n$ points with unit-height rectangles. We show how an $O(nlog n)$-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is $(2+$, it runs in $O(n^2/$ time and uses $O(n/$ space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. par For slider models we also investigate some special cases, namely (a)~the number of different point weights is bounded, (b)~all labels are unit squares, and (c)~the ratio between maximum and minimum label height is bounded.

The implementation of an algorithm is faced with the issues of efficiency, flexibility, and ease-of-use. In this paper we suggest a design concept that greatly increases the flexibility of an implementation without sacrificing ease-of-use and efficiency. par We demonstrate the advantages of our concept through a C++ implementation of a simple rectangle-intersection algorithm, which follows the well-known sweep-line paradigm. We lead the reader, who should be familiar with C++ and its template mechanism, from a naive interface in a step-by-step guide to an interface offering full flexibility. The gain in flexibility can reduce the overall implementation effort by facilitating code reuse. Reusability in turn helps to achieve correctness simply because more users mean more testing. par Though most of the ingredients of our concept have already been suggested elsewhere, to our knowledge this is the first time that they are applied vigorously in a geometric setting. We include a thorough experimental analysis on random and real-world data.

The cartographic labeling problem is the problem of placing text on a map. This includes the positioning of the labels, and determining the shape in the case of line and area feature labels. There are many rules and customs that describe aspects of good label placement, like readability and clear association. This paper gives a classification of most label placement rules, and formalizes them into a function that can serve as a quality measure for label placement. If such a function is implemented, it allows to compare the output of different label placement programs. We give a simple and a more refined example of the quality function.

Given a set $P$ of $n$ points in the plane, the two-circle point-labeling problem consists of placing $2n$ uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. par It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from $4/(1+33) approx 0.5931$ to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size. We keep the $O(n log n)$ time and $O(n)$ space bounds of the previously best algorithm.

We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50 % to about 1/20. At the same time, our algorithm keeps the $O(n log n)$ time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.

The general label-placement problem consists in labeling a set of features (points, lines, regions) given a set of candidates (rectangles, circles, ellipses, irregularly shaped labels) for each feature. The problem arises when annotating classical cartographical maps, diagrams, or graph drawings. The size of a labeling is the number of features that receive pairwise nonintersecting candidates. Finding an optimal solution, i.e., a labeling of maximum size, is NP-hard. par We present an approach to attack the problem in its full generality. The key idea is to separate the geometric part from the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates. We present a set of rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these rules with a simple heuristic yields near-optimal solutions. We study competing algorithms and do a thorough empirical comparison on point-labeling data. The new algorithm we suggest is fast, simple, and effective.

This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allow more points to be labeled both in theory and in practice. We define six different models of labeling. We compare models by analyzing how many more points can receive labels under one model than another. We show that maximizing the number of labeled points is NP-hard in the most general of the new models. Nevertheless, we give a polynomial-time approximation scheme and a simple and efficient factor-1/2 approximation algorithm for each of the new models. par Finally, we give experimental results based on the factor-1/2 approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.

The Map Labeling problem is a classical problem of cartography. There is a theoretically optimal approximation algorithm $A$. Unfortunately $A$ is useless in practice as it typically produces results that are intolerably far off the optimal size. On the other hand there are heuristics with good practical results. In this paper we present an algorithm $B$ that (a) guarantees the optimal approximation quality and runtime behaviour of $A$, and (b) yields results significantly closer to the optimum than the best heuristic known so far. The sample data used in the experimental evaluation consists of three different classes of random problems and a selection of problems arising in the production of groundwater quality maps by the authorities of the City of Munich.

A route in a network can be described as a sequence of nodes. Given a route, travellers need directions to follow it, which are preferably expressed as a sequence of instructions, as for instance, "face towards the tower" and "move along the river". This paper presents a method to find routes in a network with the property that they can be described by a simple sequence of instructions. The key problems that we need to solve are (1)~how to attribute landmark information to the network and (2)~how to find an optimal route. We approach the first problem by using landmarks as parts of instructions and mapping instructions to sets of edges in the network. The second problem can be solved by building an auxiliary graph such that a standard Dijkstra shortest path algorithm can be used to find optimal routes. Preliminary tests indicate that our approaches produce good results.

In this paper, we present boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the points. Then we connect each label to its point such that no two connections intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.

In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph $G$ such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, $s$--$t$ paths, cycles, matchings, and $-factors for $kappa in 1,2$. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k^1-varepsilon for any varepsilon > 0, where $k$ is the number of crossings in $G$. We then show that the problems are fixed-parameter tractable if we use the number of crossings in the given graph as the parameter. Finally we present a simple but effective heuristic for spanning trees.

This paper discusses a variety of ways to place diagrams like pie charts on maps, in particular, administrative subdivisions. The different ways come from different models of the placement problem: a diagram of one region should cover other regions, roads or boundaries as little as possible. In total we present six models for diagram placement. We outline three different algorithmic approaches and discuss the efficiency of each approach for the different models, and also for different types of diagrams (rectangular, circular, same or different sizes). We have implemented an algorithm for each model and show the resulting diagram placements on a number of maps. Our evaluation gives a first indication which model is best for aesthetically good diagram placement.

Graphical features on map, charts, diagrams and graph drawings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled. Even a seemingly strong simplification of the general point-labeling problem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NP-complete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it. In case of a sloping line points can be labeled with maximum-size square labels in $O(n log n)$ time if four label positions per point are allowed and in $O(n^3log n)$ time if labels can slide. We also investigate rectangular labels.

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually refered to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups; fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for unit-height labels. We give an $O(nlog n)$-time factor-2 approximation algorithm for fixed-position models and the first algorithm for labeling weighted points with sliding labels. Its approximation factor is $(2+$ and its runtime in $O(n^2/$ for any $0$.

The cartographic labeling problem is the problem of placing text on a map. It is composed of two phases. In the first, the question which map features should in principle receive a label is settled and the style (i.e. color and font) of these labels is determined. The second phase consists of the actual label placement. In this phase for each feature one has to decide whether there is in fact sufficient space and, if yes, the best location and shape of the label must be determined. This paper proposes a quality measure for the result of the second phase, allowing the comparison of label placement programs.

MakeIt! automizes the process of writing makefiles for C and C++ projects. MakeIt! supports the idea of literate programming, i.e. of keeping code and documentation in one file. From this file, a LaTeX file with the documentation and product files with the program code are extracted. All implementation files are then scanned for include statements in order to detect dependencies among them. These are written into so-called dependency files and subsequently used by the make process to ensure that products and documentation are up to date. The time overhead is small since a dependency file contains only the dependencies deduced from one file. Thus it can be reused until a change in this file occurs. par MakeIt! simplifies software development and improves the resulting software in three ways. par o MakeIt! frees the programmer's mind of the duty of writing and maintaining makefiles, par o MakeIt! simplifies (but does not depend on) the use of literate programming, and par o MakeIt! offers full support for simultaneous work on different platforms with different compilers, which is a necessity for developing portable code.