We study a geometric representation problem, where we are given a set @math of axis-aligned rectangles with fixed dimensions and a graph with vertex set @math . The task is to place the rectangles without overlap such that two rectangles touch if and only if the graph contains an edge between them. We call this problem Contact Representation of Word Networks (CROWN). It formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Here, we represent words by rectangles and semantic relationships by edges. We show that CROWN is strongly NP-hard even restricted trees and weakly NP-hard if restricted stars. We consider the optimization problem Max-CROWN where each adjacency induces a certain profit and the task is to maximize the sum of the profits. For this problem, we present constant-factor approximations for several graph classes, namely stars, trees, planar graphs, and graphs of bounded degree. Finally, we evaluate the algorithms experimentally and show that our best method improves upon the best existing heuristic by 45 .
In rectangle representations of graphs, vertices are axis-aligned rectangles with non-intersecting interiors and edges correspond to rectangles with non-zero length common boundary. Every graph that can be represented this way is planar and every triangle in such a graph is a facial triangle; these two conditions are also sufficient to guarantee a rectangle representation @cite_2 @cite_16 @cite_15 @cite_14 . In a recent survey, Felsner @cite_20 reviews many rectangulation variants, including squarings. Algorithms for area-preserving rectangular cartograms are also related @cite_7 . Area-universal rectangular representations where vertex weights are represented by area have been characterized @cite_21 and edge-universal representations, where edge weights are represented by length of contacts have been studied @cite_22 . Unlike cartograms, in our setting there is no inherent geography, and hence, words can be positioned anywhere. Moreover, each word has fixed dimensions enforced by its frequency in the input text, rather than just fixed area.
@cite_14 @cite_22 @cite_7 @cite_21 @cite_2 @cite_15 @cite_16 @cite_20
2099777423 2115023660 2322867406 2082251733 1971244706 1973624728 2082205964 24725585
This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, which are called irreducible triangulations. The structure has been introduced by Xin He under the name of regular edge-labelling and consists of two bipolar orientations that are transversal. For this reason, the terminology used here is that of transversal structures. The main results obtained in the article are a bijection between irreducible triangulations and ternary trees, and a straight-line drawing algorithm for irreducible triangulations. For a random irreducible triangulation with n vertices, the grid size of the drawing is asymptotically with high probability 11n 27x11n 27 up to an additive error of O(n). In contrast, the best previously known algorithm for these triangulations only guarantees a grid size (@?n 2@?-1)x@?n 2@?. We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. We show that for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time. If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded. T HE idea of the statistical cartogram occurred to the author when he had occasion to prepare maps of the United States showing the distribution of various economic units, such as steel factories, textile mills, power plants, banks, etc. These maps were far too crowded in the northeast to be useful, while elsewhere, for the most part, they were relatively empty. If a way could be found to increase the scale of the northeastern region and reduce that of the west, distribution could be shown more clearly. Simple distortion of the map would be misleading, but, if we go a step farther, discard altogether the outlines of the country, and give each region a rectangular form of size proportional to the value represented, we arrive at the rectangular statistical cartogram. For purposes of comparison it is essential that a definite system of construction should be followed and identical arrangement should be used whatever values are represented. The system here used starts always with the larger divisions and by "proportionate halving" arrives at the smaller ones. It should be emphasized that the statistical cartogram is not a map. Although it has roughly the proportions of the country and retains as far as possible the relative locations of the various regions, the cartogram is purely a geometrical design to visualize certain statistical facts and to work out certain problems of distribution. Examples of these cartograms are given in the accompanying figures. The division into regions follows the usage of the United States Census Bureau, because only from this source are data available. If natural geographic regions could be used instead, the cartograms would be still more instructive. A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. These layouts are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whe... We prove that every planar graph is the intersection graph of a collection of three-dimensional boxes, with intersections occuring only in the boundaries of the boxes. Furthermore, we characterize the graphs that have such representations (called strict representations) in the plane. These are precisely the proper subgraphs of 4-connected planar triangulations, which we characterize by forbidden sub-graphs. Finally, we strengthen a result of E. R. Scheinerman (“Intersection Classes and Multiple Intersection Parameters”, Ph. D. thesis, Princeton Univ., 1984) to show that every planar graph has a strict representation using at most two rectangles per vertex. Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O(n)-time algorithms that construct O(n2)-area rectangular layouts for general contact graphs and O(n log n)-area rectangular layouts for trees. (For trees, this is an O(log n)-approximation algorithm.) We also present an infinite family of graphs (respectively, trees) that require Ω(n2) (respectively, Ω(n log n))area. We derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of rectangular duals. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle-of-influence drawings. We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n---4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph. In the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular drawings, the corners of the rectangles represent the vertices. The graph obtained by taking the rectangles as vertices and contacts as edges is the rectangular dual. In visibility graphs and segment contact graphs, the vertices correspond to horizontal or to horizontal and vertical segments of the dissection. Special orientations of graphs turn out to be helpful when dealing with characterization and representation questions. Therefore, we look at orientations with prescribed degrees, bipolar orientations, separating decompositions, and transversal structures.