A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
A confluent drawing of a graph is a set of points and curves in the plane with the property that two vertices are adjacent in the graph if and only if the corresponding points can be connected to each other by smooth paths in the drawing. We define a variant of confluent drawing, strict confluent drawing, in which a smooth path between two vertices (if it exists) must be unique. We show that it is NP-complete to test whether such drawings exist, in contrast to unrestricted confluence for which the complexity remains open. Additionally, we show that finding outerplanar drawings (in which the points are on the boundary of a disk and the curves are interior to it) with a fixed cyclic vertex ordering can be performed in polynomial time. We use circle packings to find nice versions of these drawings in which all tracks are represented by piecewise-circular curves.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.