A k-page book embedding of a directed acyclic graph consists of a topological order of its vertices and a k-coloring of its edges, such that no two edges of the same color cross, that is, their endpoints do not alternate in the order. The minimum value of k for which such an embedding exists is referred to as the page number of the graph. In contrast to general directed acyclic planar graphs, which may have unbounded page number [SIAM J. Comput. 28(5), 1999], it was recently shown that directed acyclic outerplanar graphs have bounded page number. In particular, Jungeblut, Merker and Ueckerdt provided an upper bound of 24,776 on their page number [FOCS 2023: 1937-1952]. In this work, we focus on so-called monotone directed acyclic outerplanar graphs. Starting from a single edge, these graphs are constructed by iteratively connecting a new vertex to the endpoints of an existing edge on the outer face using either two incoming or two outgoing edges incident to it. These graphs have twist-number 4 [GD 2023: 135-151] (i.e., they admit a topological order in which no more than four edges pairwise cross), a property, which was leveraged by Jungeblut, Merker and Ueckerdt to show that their page number is at most 128. We lower this upper bound to 5 and we also provide a lower bound of 4. A notable consequence of our result is a significant improvement of the upper bound on the page number of general directed outerplanar graphs from 24,776 to 1,160.

Abstract We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width $$w=2$$ w = 2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width $$w > 2$$ w > 2 . Our analysis implies an upper bound of $$(w-1)^2 +1$$ ( w - 1 ) 2 + 1 on the queue number of width-w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least $$w+1$$ w + 1 queues in every linear extension, thereby disproving the conjecture for posets of width $$w > 2$$ w > 2 .

We investigate the memorability of two types of cartograms, both in terms of recognition of the visualization and recall of the data. A cartogram, or a value-by-area map, is a representation of a map in which geographic regions are modified to reflect a given statistic, such as population or income. Of the many different types of cartograms, the contiguous and Dorling types are among the most popular and most effective. With this in mind, we evaluate the memorability of these two cartogram types with a human-subjects study, using task-based experimental data and cartogram visualization tasks based on Bertin's map reading levels. In particular, our results indicate that Dorling cartograms are associated with better recall of general patterns and trends. This, together with additional significant differences between the two most popular cartogram types, has implications for the design and use of cartograms, in the context of memorability.

Abstract A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues , so that no two independent edges of the same queue are nested. The queue number of graph G is defined as the minimum number of queues required by any queue layout of G . In this paper, we continue the study of the queue number of planar 3-trees, which form a well-studied subclass of planar graphs. Prior to this work, it was known that the queue number of planar 3-trees is at most seven. In this work, we improve this upper bound to five. We also show that there exist planar 3-trees whose queue number is at least four. Notably, this is the first example of a planar graph with queue number greater than three.

Cartograms are maps in which areas of geographic regions, such as countries and states, appear in proportion to some variable of interest, such as population or income. Cartograms are popular visualizations for geo-referenced data that have been used for over a century to illustrate patterns and trends in the world around us. Despite the popularity of cartograms, and the large number of cartogram types, there are few studies evaluating the effectiveness of cartograms in conveying information. Based on a recent task taxonomy for cartograms, we evaluate four major types of cartograms: contiguous, non-contiguous, rectangular, and Dorling cartograms. We first evaluate the effectiveness of these cartogram types by quantitative performance analysis (time and error). Second, we collect qualitative data with an attitude study and by analyzing subjective preferences. Third, we compare the quantitative and qualitative results with the results of a metrics-based cartogram evaluation. Fourth, we analyze the results of our study in the context of cartography, geography, visual perception, and demography. Finally, we consider implications for design and possible improvements.

We describe bivariate cartograms, a technique specifically designed to allow for the simultaneous comparison of two geo-statistical variables. Traditional cartograms are designed to show only a single statistical variable, but in practice, it is often useful to show two variables (e.g., the total sales for two competing companies) simultaneously. We illustrate bivariate cartograms using Dorling-style cartograms, yet the technique is simple and generalizable to other cartogram types, such as contiguous cartograms, rectangular cartograms, and non-contiguous cartograms. An interactive feature makes it possible to switch between bivariate cartograms, and the traditional (monovariate) cartograms. Bivariate cartograms make it easy to find more geographic patterns and outliers in a pre-attentive way than previous approaches, as shown in Fig. 2 . They are most effective for showing two variables from the same domain (e.g., population in two different years, sales for two different companies), although they can also be used for variables from different domains (e.g., population and income). We also describe a small-scale evaluation of the proposed techniques that indicates bivariate cartograms are especially effective for finding geo-statistical patterns, trends and outliers.

We describe a security visualization tool for finding algorithmic complexity attacks in Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs derived from Java bytecode according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. The particular graphs we consider are derived from applying Shiver's k-CFA framework to Java bytecode, and our visualizer includes helpful links between the nodes of an input graph and the Java bytecode that produced it, as well as a decompiled version of that Java bytecode. We show through experiments involving test cases provided by DARPA that the canonical drawing paradigm used in J-Viz is effective for identifying potential security vulnerabilities for algorithmic complexity attacks.

Abstract Cartograms are used to visualize geographically distributed data by scaling the regions of a map (e.g., US states) such that their areas are proportional to some data associated with them (e.g., population). Thus the cartogram computation problem can be considered as a map deformation problem where the input is a planar polygonal map M and an assignment of some positive weight for each region. The goal is to create a deformed map M′, where the area of each region realizes the weight assigned to it (no cartographic error) while the overall map remains readable and recognizable (e.g., the topology, relative positions and shapes of the regions remain as close to those before the deformation as possible). Although several such measures of cartogram quality are well‐known, different cartogram generation methods optimize different features and there is no standard set of quantitative metrics. In this paper we define such a set of seven quantitative measures, designed to evaluate how faithfully a cartogram represents the desired weights and to estimate the readability of the final representation. We then study several cartogram‐generation algorithms and compare them in terms of these quantitative measures.

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.