Search

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM J. Discrete Math., 5 (1992), pp. 398--412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number. [ABSTRACT FROM AUTHOR]

This paper presents OpMAP: a tool for visualizing large scale, multi-dimensional opinion spaces as geographic maps. OpMAP represents opinions as labelings on a structured deductive argumentation framework. It uses probabilistic degrees of justification and Bayesian coherence measures to calculate how strongly any two opinions cohere with each other. The opinion sample is, accordingly, represented as a weighted graph, a so-called opinion graph, with opinion vectors serving as nodes and coherence values as edge weights. OpMAP partitions the nodes of the opinion graph by using clustering methods. Finally, the graph is visualized as a geographic map using a method based on a particular (e.g., force-directed) layout. [ABSTRACT FROM AUTHOR]

Positive effects of aesthetically appreciated designs have long been studied and confirmed since the 19th century: such designs are more enjoyable, they are more forgivable for glitches and can increase users’ performance. In the field of information visualization, studies of aesthetics are still a niche approach. In the current study, we aim to specifically understand which parameters in a visualization of node-link diagrams make them aesthetically pleasing-an important extension to already existing research on usability and readability aspects. We investigated how the shape of the outline of such diagrams influences the aesthetic judgments on two of the most important dimensions of aesthetic appeal: beauty and interest. We employed different outlines to node-link diagrams and compared them with uniformly filled shapes, varying two important variables typically impacting aesthetics: complexity and curvature. This was done for a short (100 ms) and ad libitum presentation time. Diagrams with curvier outlines were perceived as more beautiful, while diagrams with more complex outlines were considered to be more interesting. These dependencies already exist for presaccadic perception (100 ms) and are slightly stronger for unlimited presentation time. We also found that curvature is a predictor for beauty only for unlimited presentation time. Aesthetic appeal was very similar for diagrams and pure shapes, so many results from fundamental research on aesthetics can potentially be transferred to the community of network visualization, assisting to improve visualizations also in aesthetic regards. [ABSTRACT FROM AUTHOR]

A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other partition, together with the edges, must be added to the drawing without any restriction on their positions. We assume that G is planar and study the problem of finding a planar straight-line drawing of G. We show that deciding whether G admits such a drawing is NP -hard in the general case. Under the assumption that each mobile vertex is placed in the convex hull of its neighbors, we are able to prove that the problem is also in NP. Moreover, if the intersection graph of these convex hulls is a path, a cycle or, more generally, a cactus, the problem is polynomial-time solvable through a dynamic programming approach. Finally, we describe linear-time testing algorithms when the fixed vertices are collinear or when they lie on a finite set of horizontal levels (lines) and no edge can intersect a level except at its fixed vertex. [ABSTRACT FROM AUTHOR]

A drawing of a graph is greedy if for each ordered pair of vertices u and v , there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. From an application perspective, greedy drawings are especially relevant to support routing schemes in ad hoc wireless networks. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings , where edges are horizontal or vertical segments. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation , i.e., a plane graph with prescribed vertex angles, admits a greedy rectilinear drawing. We give a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances. [ABSTRACT FROM AUTHOR]