We present an algorithm for finding the minimum cut of an undirected edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement, and has a surprisingly simple proof of correctness. Its runtime matches that of the fastest algorithm known. The runtime analysis is straightforward. In contrast to nearly all approaches so far, the algorithm uses no flow techniques. Roughly speaking, the algorithm consists of about | V | nearly identical phases each of which is a maximum adjacency search .

The lettering of maps is a classical problem of cartography that consists of placing names, symbols, or other data near to specified sites on a map. Certain design rules have to be obeyed. A practically interesting special case, the Map Labeling Problem, consists of placing axis parallel rectangular labels of common size so that one of its corners is the site, no two labels overlap, and the labels are of maximum size in order to have legible inscriptions. The problem is NP-hard; it is even NP-hard to approximate the solution with quality guaranty better than 50 percent. There is an approximation algorithm A with a quality guaranty of 50 percent and running time O (n log n). So A is the best possible algorithm from a theoretical point of view. This is even true for the running time, since there is a lower bound on the running time of any such approximation algorithm of (n log n). Unfortunately A is useless in practice as it typically produces results that are intolerably far off the maximum size. The main contribution of this paper is the presentation of a heuristical approach that has A's advantages while avoiding its disadvantages: 1\. It uses A's result in order to guaranty the same optimal running time efficiency; a method which is new as far as we know. 2\. Its practical results are close to the optimum. The practical quality is analysed by comparing our results to the exact optimum, where this is known; and to lower and upper bounds on the optimum otherwise. The sample data 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 München.

Presents a global approach to solve the three-layer wirability problem for knock-knee layouts. In general, the problem is NP-complete. Only for very restricted classes of layouts polynomial three-layer wiring algorithms are known up to now. The authors show that for a large class of layouts a three-layer wiring can be constructed by solving a path problem in a special class of graphs or a two-satisfiability problem, and thus may be wired in time linear in the size of the layout area. Moreover, it is shown that a minimum stretching of the layout into a layout belonging to this class can be found by solving a clique cover problem in an interval graph. This problem is solvable in time linear in the size of the layout area as well. Altogether, the method also yields a good heuristic for the three-layer wirability problem for knock-knee layouts.>

The following packing problem arises in connection with lettering of maps: Given n distinct points pl, p2,.... pn in the plane, determine the supremum uoPi of all reals U, such that there are n pan-wise dtsjomt, axis-parallel, closed squares Ql, Q2,.... Qn of side-length u, where each pi ts a corner of Qi. Note that — by using afine transformation — the problem is equivalent to the case when we want largest homothetic cop~es of a jized rectangle or parallelogram tnstead of equal ly-szzed squares. In the cartographic application, the points are items (groundwater-drillho les etc.) and the squares are places for labels associated with these items (sulphate concentration etc.). An algorithm is presented, that in O(n log n] time either produces a solution, that is guaranteed to be at least half as large as the supremum. This is optimal, m the sense that the corresponding decision problem is NP-complete, no po[ynomzal approximation algorithm with a guaranteed factor ezceedmg ~ exwts, provided that P # AfP; and there M also a lower bound of C2(n log n) for the running time. 1

The channel routing problem in the knock-knee mode is considered. The algorithm presented always constructs a correct layout in a channel of bounded size, if there is one, and guarantees that it is wirable with only three conducting layers; that is, the layout is optimal with respect to the area and to the number of layers. The algorithm thus improves all previously known layout algorithms, which either use additional columns to produce a three-layer wirable layout or construct a layout for which the three-layer wirability is not proved. For the layer assignment only O(N) (N is the number of nets) vias are used. The algorithm can be implemented to run in O(N log N) time.>