We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.
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".
We study the problem of matching geographic regions to points in a regular grid, minimizing the distance between each region's centroid and the corresponding grid point, and preserving as much as possible the relative orientations between pairs of regions.
A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".
Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.