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 .
Hierarchically clustered document collections are visualized with self-organizing maps @cite_4 and Voronoi treemaps @cite_3 . The early word-cloud approaches did not explicitly use semantic information, such as word relatedness, in placing the words in the cloud. More recent approaches attempt to do so, as in ManiWordle @cite_13 and in parallel tag clouds @cite_0 . The most relevant approaches rely on force-directed graph visualization methods @cite_8 and a seam-carving image processing method together with a force-directed heuristic @cite_12 . The semantics-preserving word cloud problem is related to classic graph layout problems, where the goal is to draw graphs so that vertex labels are readable and Euclidean distances between pairs of vertices are proportional to the underlying graph distance between them. Typically, however, vertices are treated as points and label overlap removal is a post-processing step @cite_6 @cite_18 .
@cite_18 @cite_4 @cite_8 @cite_3 @cite_6 @cite_0 @cite_13 @cite_12
2098329200 2156985538 1970773000 1990402145 1584926591 2075038621 2141558464 2122580360
When drawing graphs whose nodes contain text or graphics, the nontrivial node sizes must be taken into account, either as partof the initial layout or as a post-processing step. The core problem in avoiding or removing overlaps is to retain the structural information inherent in a layout while minimizing the additional area required. Thispaper presents a new node overlap removal algorithm that does well at retaining a graph’s shape while using little additional area and time. As part ofthe analysis, we consider and evaluate two measures of dissimilarity for two layouts of the same graph. Powerful methods for interactive exploration and search from collections of free-form textual documents are needed to manage the ever-increasing flood of digital information. In this article we present a method, WEBSOM, for automatic organization of full-text document collections using the self-organizing map (SOM) algorithm. The document collection is ordered onto a map in an unsupervised manner utilizing statistical information of short word contexts. The resulting ordered map where similar documents lie near each other thus presents a general view of the document space. With the aid of a suitable (WWW-based) interface, documents in interesting areas of the map can be browsed. The browsing can also be interactively extended to related topics, which appear in nearby areas on the map. Along with the method we present a case study of its use. In this paper, we introduce a visualization method that couples a trend chart with word clouds to illustrate temporal content evolutions in a set of documents. Specifically, we use a trend chart to encode the overall semantic evolution of document content over time. In our work, semantic evolution of a document collection is modeled by varied significance of document content, represented by a set of representative keywords, at different time points. At each time point, we also use a word cloud to depict the representative keywords. Since the words in a word cloud may vary one from another over time (e.g., words with increased importance), we use geometry meshes and an adaptive force-directed model to lay out word clouds to highlight the word differences between any two subsequent word clouds. Our method also ensures semantic coherence and spatial stability of word clouds over time. Our work is embodied in an interactive visual analysis system that helps users to perform text analysis and derive insights from a large collection of documents. Our preliminary evaluation demonstrates the usefulness and usability of our work. We propose a method to highlight query hits in hierarchically clustered collections of interrelated items such as digital libraries or knowledge bases. The method is based on the idea that organizing search results similarly to their arrangement on a fixed reference map facilitates orientation and assessment by preserving a user's mental map. Here, the reference map is built from an MDS layout of the items in a Voronoi treemap representing their hierarchical clustering, and we use techniques from dynamic graph layout to align query results with the map. The approach is illustrated on an archive of newspaper articles. The problem of node overlap removal is to adjust the layout generated by typical graph drawing methods so that nodes of non-zero width and height do not overlap, yet are as close as possible to their original positions. We give an O(n log n) algorithm for achieving this assuming that the number of nodes overlapping any single node is bounded by some constant. This method has two parts, a constraint generation algorithm which generates a linear number of “separation” constraints and an algorithm for finding a solution to these constraints “close” to the original node placement values. We also extend our constraint solving algorithm to give an active set based algorithm which is guaranteed to find the optimal solution but which has considerably worse theoretical complexity. We compare our method with convex quadratic optimization and force scan approaches and find that it is faster than either, gives results of better quality than force scan methods and similar quality to the quadratic optimisation approach. Do court cases differ from place to place? What kind of picture do we get by looking at a country's collection of law cases? We introduce Parallel Tag Clouds: a new way to visualize differences amongst facets of very large metadata-rich text corpora. We have pointed Parallel Tag Clouds at a collection of over 600,000 US Circuit Court decisions spanning a period of 50 years and have discovered regional as well as linguistic differences between courts. The visualization technique combines graphical elements from parallel coordinates and traditional tag clouds to provide rich overviews of a document collection while acting as an entry point for exploration of individual texts. We augment basic parallel tag clouds with a details-in-context display and an option to visualize changes over a second facet of the data, such as time. We also address text mining challenges such as selecting the best words to visualize, and how to do so in reasonable time periods to maintain interactivity. Among the multifarious tag-clouding techniques, Wordle stands out to the community by providing an aesthetic layout, eliciting the emergence of the participatory culture and usage of tag-clouding in the artistic creations. In this paper, we introduce ManiWordle, a Wordle-based visualization tool that revamps interactions with the layout by supporting custom manipulations. ManiWordle allows people to manipulate typography, color, and composition not only for the layout as a whole, but also for the individual words, enabling them to have better control over the layout result. We first describe our design rationale along with the interaction techniques for tweaking the layout. We then present the results both from the preliminary usability study and from the comparative study between ManiWordle and Wordle. The results suggest that ManiWordle provides higher user satisfaction and an efficient method of creating the desired "art work," harnessing the power behind the ever-increasing popularity of Wordle. Word clouds are proliferating on the Internet and have received much attention in visual analytics. Although word clouds can help users understand the major content of a document collection quickly, their ability to visually compare documents is limited. This paper introduces a new method to create semantic-preserving word clouds by leveraging tailored seam carving, a well-established content-aware image resizing operator. The method can optimize a word cloud layout by removing a left-to-right or top-to-bottom seam iteratively and gracefully from the layout. Each seam is a connected path of low energy regions determined by a Gaussian-based energy function. With seam carving, we can pack the word cloud compactly and effectively, while preserving its overall semantic structure. Furthermore, we design a set of interactive visualization techniques for the created word clouds to facilitate visual text analysis and comparison. Case studies are conducted to demonstrate the effectiveness and usefulness of our techniques.