We present a new circular-arc cartogram model in which countries are drawn as polygons with circular arcs instead of straight-line segments. Given a political map and values associated with each country in the map, a cartogram is a distorted map in which the areas of the countries are proportional to the corresponding values. In the circular-arc cartogram model straight-line segments can be replaced by circular arcs in order to modify the areas of the polygons, while the corners of the polygons remain fixed. The countries in circular-arc cartograms have the aesthetically pleasing appearance of clouds or snowflakes, depending on whether their edges are bent outwards or inwards. This makes it easy to determine whether a country has grown or shrunk, just by its overall shape. We show that determining whether a given map and given area-values can be realized as a circular-arc cartogram is an NP-hard problem. Next we describe a heuristic method for constructing circular-arc cartograms, which uses a max-flow computation on the dual graph of the map, along with a computation of the straight skeleton of the underlying polygonal decomposition. Our method is implemented and produces cartograms that, while not yet perfectly accurate, achieve many of the desired areas in our real-world examples.
The problem of representing additional information on top of a geographic map dates back to the 19th century, and highly schematized rectangular cartograms can be found in the 1934 work of Raisz @cite_20 . With rectangular cartograms it is not always possible to preserve all country adjacencies and realize all areas accurately @cite_27 @cite_25 . Eppstein studied area-universal rectangular layouts and characterized the class of rectangular layouts for which all area-assignments can be achieved with combinatorially equivalent layouts @cite_21 . If the requirement that rectangles are used is relaxed to allow the use of rectilinear regions then de Berg @cite_22 showed that all adjacencies can be preserved and all areas can be realized with 40-sided regions. In a series of papers the polygon complexity that is sufficient to realize any rectilinear cartogram was decreased from 40 over 34 corners @cite_18 , 12 corners @cite_23 , 10 corners @cite_15 down to 8 corners @cite_24 , which is best possible due to the earlier lower bound of 8-sided regions @cite_11 .
@cite_18 @cite_22 @cite_21 @cite_24 @cite_27 @cite_23 @cite_15 @cite_25 @cite_20 @cite_11
2010712298 2043148321 190320872 2002025203
In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the rst part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of 3-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeo between redundancy and access overhead. In the second part of the paper, we develop dynamic external memory data structures for the two query types. Our structure for 3-sided queries occupies O(N=B) disk blocks, and it supports insertions and deletions in O(log B N) I Os and queries in O(log B N + T=B) I Os, where B is the disk block size, N is the number of points, and T is the query output size. These bounds are optimal. Our structure for general (4-sided) range searching occupies O (N=B)(log(N=B))= log log B N disk blocks and answers queries in O(log B N + T=B) I Os, which are optimal. It also supports updates in O (log B N)(log(N=B))= log log B N I Os. Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708 0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04 96 1 0013 and by the National Science Foundation through ESS grant EIA 9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark. Email: large@cs.duke.edu. yDepartment of Computer Sciences, University of Texas at Austin, Austin, TX 78712-1188. Email vsam@cs.utexas.edu zCenter for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708 0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04 96 1 0013 and by the National Science Foundation through grants CCR 9522047 and EIA 9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark and I.N.R.I.A., Sophia Antipolis, France. Email: jsv@cs.duke.edu. This paper presents work in progress on a new technique for visu- alising and manipulating large hierarchies. The information slices approach compactly visualises hierarchical structures using a series of semi-circular discs. The technique is described in the context of our early experience with a prototype file system visualiser based on information slices. Over the last few years, the emerging field of information visuali- sation has resulted in a numerous techniques for helping visualise and make sense of large information spaces (10). Among these are several techniques for visualising and interacting with large hierar- chies which go beyond the traditional approach taken in 2d scrolling browsers such as the Windows Explorer. Treemaps (6, 9) are space-filling visualisations of hierarchies based on successive horizontal and vertical subdivision of screen rectangles. The area of each rectangle is proportional to some at- tribute of the underlying hierarchy such as the (total) size of each subtree. Xdu (4) is a utility for the X window system which displays a graphical disk usage for Unix file systems. Rectangles are stacked from left to right as the directory tree is descended. The current di- rectory is represented by the leftmost rectangle, which is the entire height of the window. Subdirectories are represented by neighbour- ing rectangles in the next column, whose height are proportional to the size of each subdirectory. The hyperbolic browser (7) uses a focus and context technique based on hyperbolic geometry. A hierarchy is laid out uniformly on the hyperbolic plane and then mapped to the unit disc for display on screen. Nodes in the centre of the disc are largest and nodes are assigned progressively less space towards the perimeter of the disc. Cheops (3) is based on multiple re-use of overlaid triangles in the display. Working top-down, the selection of a node (triangle) at a particular level designates that node's children are to be represented Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time @math , where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of @math degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams.