Problem solving is a composite cognitive process, invoking a number of cognitive mechanisms, such as perception and memory. Individuals may form collectives to solve a given problem together in collaboration, especially when complexity is perceived to be high. To determine if and when collaborative problem solving is desired in the context of visual graph analysis, we compare ad hoc pairs to individuals and nominal pairs, when solving different tasks in mixed reality. We discuss the results of an experiment with 72 participants performed in two countries and three languages. We apply the concept of task instance complexity to quantify the visual demand of tasks used in the experiment. Our results show the importance of using nominal groups as a benchmark for evaluating collaborative virtual environments. We conclude that 3D graph representation is not sufficient to induce better collaborative results compared to the benchmark.

A linear layout of a graph defines a total order of the vertices and partitions the edges into either stacks or queues, i.e., crossing-free and non-nested sets of edges along the order, respectively. In this work, we study defective linear layouts that allow forbidden patterns among edges of the same set. Our focus is on k-defective stack layouts and k-defective queue layouts, in which the conflict graph representing the forbidden patterns among the edges of each stack or queue has maximum degree at most k.

A linear layout of a graph consists of a linear ordering of its vertices and a partition of its edges into pages such that the edges assigned to the same page obey some constraint. The two most prominent and widely studied types of linear layouts are stack and queue layouts, in which any two edges assigned to the same page are forbidden to cross and nest, respectively. The names of these two layouts derive from the fact that, when parsing the graph according to the linear vertex ordering, the edges in a single page can be stored using a single stack or queue, respectively. Recently, the concepts of stack and queue layouts have been extended by using a double-ended queue or a restricted-input queue for storing the edges of a page. We extend this line of study to edge-weighted graphs by introducing priority queue layouts, that is, the edges on each page are stored in a priority queue whose keys are the edge weights. First, we show that there are edge-weighted graphs that require a linear number of priority queues. Second, we characterize the graphs that admit a priority queue layout with a single queue, regardless of the edge-weight function, and we provide an efficient recognition algorithm. Third, we show that the number of priority queues required independently of the edge-weight function is bounded by the pathwidth of the graph, but can be arbitrarily large already for graphs of treewidth two. Finally, we prove that determining the minimum number of priority queues is NP-complete if the linear ordering of the vertices is fixed.

The edge-length ratio of a planar straight-line drawing Γ of a graph G is the largest ratio between the lengths of every pair of edges of Γ. If the ratio is measured by considering only pairs of edges that are incident to a common vertex, we talk about local edge-length ratio. The (local) edge-length ratio of a planar graph is the infimum over all (local) edge-length ratios of its planar straight-line drawings. It is known that the edge-length ratio of outerplanar graphs is upper bounded by a constant, while there exist graph families with non-constant outerplanarity that have non-constant lower bounds on their edge-length ratios. In this paper we prove an Ω ( n ) lower bound on the local edge-length ratio (and hence on the edge-length ratio) of the n -vertex 2-outerplanar graphs. We also prove a constant upper bound on the edge-length ratio of Halin graphs, pseudo-Halin graphs, and their generalizations.

A drawing of a graph divides the plane into topologically connected regions, called faces (or cells ). The boundary of each face is formed by vertices, crossings, and edge portions. Given a positive integer , we say that is a -real face drawing of if the boundary of each face of contains at least vertices of . Graphs that admit a -real face drawing are -real face graphs ; they have been studied so far in terms of edge density and inclusion relationships with other notable classes of nonplanar graphs that can be drawn avoiding specific crossing configurations. In this paper, we investigate the complexity of recognizing -real face graphs, that is, the complexity of testing whether a given graph is -real face, for desired values of . We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are drawn as straight-line segments. While we prove NP-completeness results for the unconstrained scenario, we describe efficient recognition algorithms for the 2-layer setting.

Abstract The planar slope number $${{\,\textrm{psn}\,}}(G)$$ psn ( G ) of a planar graph G is the minimum number of edge slopes in a planar straight-line drawing of G. It is known that $${{\,\textrm{psn}\,}}(G) \in O(c^{\Delta })$$ psn ( G ) ∈ O ( c Δ ) for every planar graph G of maximum degree $$\Delta $$ Δ . This upper bound has been improved to $$O(\Delta ^5)$$ O ( Δ 5 ) if G has treewidth three, and to $$O(\Delta )$$ O ( Δ ) if G has treewidth two. In this paper we prove $${{\,\textrm{psn}\,}}(G) \le \max \{4,\Delta \}$$ psn ( G ) ≤ max { 4 , Δ } when G is a Halin graph, and thus has treewidth three. Furthermore, we present the first polynomial upper bound on the planar slope number for a family of graphs having treewidth four. Namely we show that $$O(\Delta ^2)$$ O ( Δ 2 ) slopes suffice for nested pseudotrees.

Abstract Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601–625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number b of bends, the number k of vertices of degree at most two, and the treewidth $$\textsf{tw}$$ tw of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129–148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by $$b+k$$ b + k . As a consequence, rectilinear planarity testing lies in FPT parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most b bends exists is already NP-hard when k is zero (i.e., the problem is para-NP-hard parameterized in k); hence, there is neither an FPT nor an XP algorithm parameterized only by the parameter k (unless P = NP). In addition, we prove that the problem is W[1]-hard parameterized by $$k+\textsf{tw}$$ k + tw , complementing a recent result (Jansen et al. in Upward and orthogonal planarity are W[1]-hard parameterized by treewidth. CoRR, abs/2309.01264, 2023; in: Bekos MA, Chimani M (eds) Graph Drawing and Network Visualization, vol 14466, Springer, Cham, pp 203–217, 2023) that shows W[1]-hardness for the parameterization $$b+\textsf{tw}$$ b + tw . As a consequence, we are able to trace a clear parameterized tractability landscape for the bend-minimum orthogonal planarity problem with respect to the three parameters b, k, and $$\textsf{tw}$$ tw .

We study the problem of representing a graph as a storyplan, a recently introduced model for dynamic graph visualization. It is based on a sequence of frames, each showing a subset of vertices and a planar drawing of their induced subgraphs, where vertices appear and disappear over time. Namely, in the StoryPlan problem, we are given a graph and we want to decide whether there exists a total vertex appearance order for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of the input graph. We prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete if the vertex appearance order is given and we have to choose how to draw the frames.

Hybrid visualizations combine different metaphors into a single network layout, in order to help humans in finding the "right way" of displaying the different portions of the network, especially when it is globally sparse and locally dense. We investigate hybrid visualizations in two complementary directions: (i) On the one hand, we evaluate the effectiveness of different hybrid visualization models through a comparative user study; (ii) On the other hand, we estimate the usefulness of an interactive visualization that integrates all the considered hybrid models together. The results of our study provide some hints about the usefulness of the different hybrid visualizations for specific tasks of analysis and indicates that integrating different hybrid models into a single visualization may offer a valuable tool of analysis.

Abstract A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for $$k=1$$ k = 1 and NP-complete for $$k = 6$$ k = 6 . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for $$k\ge 3$$ k ≥ 3 , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar st-graphs, closes the question about the complexity of the kUBE problem for any k. Motivated by this hardness result, we then focus on the 2UBE Testing for planar st-graphs. On the algorithmic side, we present an $$O(f(\beta )\cdot n+n^3)$$ O ( f ( β ) · n + n 3 ) -time algorithm for 2UBE Testing, where $$\beta $$ β is the branchwidth of the input graph and f is a singly-exponential function on $$\beta $$ β . Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for st-graphs of bounded treewidth. Furthermore, we describe an O(n)-time algorithm to test whether a plane st-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input st-graph. On the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving $$2$$ 2 UBE.

We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.

Abstract We study universal sets of slopes for computing upward planar drawings of planar st-graphs. We first consider a subfamily of planar st-graphs, called bitonic st-graphs. We prove that every set $$\mathcal {S}$$ S of $$\varDelta $$ Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree $$\varDelta $$ Δ , i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in $$\mathcal {S}$$ S . This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of $$\mathcal {S}$$ S , it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set $$\mathcal {S}$$ S can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most $$4n-9$$ 4 n - 9 bends in total.

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.

We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $k\geq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $β$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(β)\cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $β$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.

Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma partially preserves the topology of G if it has the same external boundary, the same rotation system, and the same set of crossings as G. Drawing Gamma fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We show that if the set of crossing-free edges of G forms a connected spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). Concerning drawings that fully preserve the topology, we show that if G has skewness k, it admits one such drawing with curve complexity at most 2k; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

We study the problem of computing drawings of planar graphs in sub-quadratic area, by allowing edge crossings. We first prove that sub-quadratic area cannot be achieved if only a constant number of crossings per edge is allowed. More precisely, we show that the same area lower bounds as in the crossing-free case hold for straight-line and poly-line drawings of planar graphs and series-parallel graphs. Motivated by this result, we study straight-line drawings of planar graphs where the number of crossings per edge is not bounded by a constant. In this case, we prove that every planar graph admits a straight-line drawing with sub-quadratic area and sub-linear thickness (the thickness of a drawing is the minimum number of colors that can be assigned to the edges so that each color class induces a planar drawing). We also prove that every partial 2-tree (and hence every series-parallel graph) admits a linear-area straight-line drawing with thickness at most 10. It is worth remarking that a drawing with thickness h−1 is h-quasi planar, i.e. it does not contain h-mutually crossing edges. The main ingredient to prove our results is (c, t)-track layouts, a combinatorial tool that can be represented as a drawing where: (i) each vertex is assigned to one of t horizontal layers (tracks), (ii) no two adjacent vertices are on the same track, (iii) each edge receives one of c colors, so that no two edges of the same color (u, v) and (w, z) cross if u, w are on the same track, and v, z are on the same track.

A 2-layer drawing of a bipartite graph G is a drawing such that the vertices of each partition set are drawn as points of a distinct horizontal line (called a layer) and the edges are drawn as straight-line segments. We study 2-layer drawings where edges can cross only at right angles; these drawings are called 2-layer right angle crossing drawings (2-layer RAC drawings for short). We focus on the following problem, which we call the maximum 2-layer RAC subgraph (M2LRacS) problem. Given a bipartite graph G, compute a subgraph H of G such that: (i) H admits a 2-layer RAC drawing and (ii) H has the maximum number of edges among the subgraphs of G that satisfy (i). We study this problem both in the no-fixed-layer setting, where no restriction is given on the vertex ordering on each layer, and in the 1-fixed-layer setting, where the ordering of the vertices of one of the two layers is given as part of the input and cannot be changed. The M2LRacS problem is known to be 𝒩𝒫-hard in the no-fixed-layer setting (Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2011) 2-Layer Right Angle Crossing Drawings. Proc. IWOCA 2011, Lecturer Notes in Computer Science 7056, pp. 156–169; Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2014) 2-layer right angle crossing drawings. Algorithmica, 68, 954–997), but no algorithm has been proposed so far to solve it. We prove that the M2LRacS problem remains 𝒩𝒫-hard even in the 1-fixed-layer setting, and provide different heuristics to solve it in the two settings; one of these heuristics is a 3-approximation algorithm for the no-fixed-layer setting. Also, we present the results of an experimental study that compares our heuristics and shows the effectiveness of the 3-approximation algorithm in practice.

A simultaneous geometric embedding (SGE) of two planar graphs |$G_1$| and |$G_2$| with the same vertex set is a pair of straight-line planar drawings |$\Gamma _1$| of |$G_1$| and |$\Gamma _2$| of |$G_2$| such that each vertex is drawn at the same point in |$\Gamma _1$| and |$\Gamma _2$|⁠. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where |$\Gamma _1$| and |$\Gamma _2$| are required to be quasi-planar (i.e. they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up several new interesting research questions.

Let [Formula: see text] be a directed acyclic graph (DAG). An upward [Formula: see text]-topological book embedding of [Formula: see text] is an upward book embedding on [Formula: see text] pages of a subdivision of [Formula: see text] where every edge is replaced by a path having at most [Formula: see text] vertices. In this paper it is proved that every DAG with [Formula: see text] vertices admits an upward ([Formula: see text], [Formula: see text])-topological book embedding, where [Formula: see text] is any integer such that [Formula: see text]. The result extends to the upward case well-known theorems for topological book embeddings of undirected graphs [H. Enomoto and M. S. Miyauchi, SIAM J. Discrete Math., 12 (1999), pp. 337–341], [M. S. Miyauchi, IEICE Transactions, 88-A (2005), pp. 1136–1139].

This paper shortly describes a system, called VisForFraud, that uses Information Visualization techniques for the discovery of financial crimes.

The paper describes WhatsOnWeb+, a search clustering engine that allows users to browse and analyze the results of a query by means of enhanced graph visualization techniques. WhatsOnWeb+ integrates a wide array of visual interfaces, animation and interaction functionalities, and clustering technologies. The effectiveness of the different visual interfaces and of the different clustering algorithms implemented in the system has been measured by means of an extensive experimental analysis. The described system represents a significant evolution of a previous clustering engine for the Web.

One of the most challenging issues in mining information from the World Wide Web is the design of systems that present the data to the end user by clustering them into meaningful semantic categories. We show that the analysis of the results of a clustering engine can significantly take advantage of enhanced graph drawing and visualization techniques. We propose a graph-based user interface for Web clustering engines that makes it possible for the user to explore and visualize the different semantic categories and their relationships at the desired level of detail.