• In this paper we study a variant of Vertex Cover where the activities of vertices are characterized by time intervals. We explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer, and the objective is to maximize the number of (temporal) edges that are covered. • We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted conditions where: the temporal domain comprises only two timestamps and each edge appears at most once and; no two edges are associated to a same label. • We delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: the number k of temporal edges covered by the solution, and the number h of temporal edges left uncovered by the solution. • We focus again on the approximability of the problem and present a polynomial-time approximation algorithm achieving a factor of 3 4 . Different variants of Vertex Cover have recently garnered attention in the context of temporal graphs. One of these variants is motivated by the need to summarize timeline activities in social networks. Here, the activities of individual vertices, representing users, are characterized by time intervals. In this paper, we explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer ℓ, and the objective is to maximize the number of (temporal) edges that are covered. We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted conditions where: the temporal domain comprises only two timestamps and each edge appears at most once and; no two edges are associated to a same label. Subsequently, we delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: (i) the number k of temporal edges covered by the solution, and (ii) the number h of temporal edges not covered by the solution. Finally, we present a polynomial-time approximation algorithm achieving a factor of 3 4 .

Our work contributes to the fast-growing literature on the use of Large Language Models (LLMs) to perform graph-related tasks. In particular, we focus on usage scenarios that rely on the visual modality, feeding the model with a drawing of the graph under analysis. We investigate how the model's performance is affected by the chosen layout paradigm, the aesthetics of the drawing, and the prompting technique used for the queries. We formulate three corresponding research questions and present the results of a thorough experimental analysis. Our findings reveal that choosing the right layout paradigm and optimizing the readability of the input drawing from a human perspective can significantly improve the performance of the model on the given task. Moreover, selecting the most effective prompting technique is a challenging yet crucial task for achieving optimal performance.

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.

Storyline visualizations represent character interactions over time. When these characters belong to different groups, a new research question emerges: how can we balance optimization of readability across the groups while preserving the overall narrative structure of the story? Traditional algorithms that optimize global readability metrics (like minimizing crossings) can introduce quality biases between the different groups based on their cardinality and other aspects of the data. Visual consequences of these biases are: making characters of minority groups disproportionately harder to follow, and visually deprioritizing important characters when their curves become entangled with numerous secondary characters. We present F2Stories, a modular framework that addresses these challenges in storylines by offering three complementary optimization modes: (1) fairnessMode ensures that no group bears a disproportionate burden of visualization complexity regardless of their representation in the story; (2) focusMode allows prioritizing a group of characters while maintaining good readability for secondary characters; and (3) standardMode globally optimizes classical aesthetic metrics. Our approach is based on Mixed Integer Linear Programming (MILP), offering optimality guarantees, precise balancing of competing metrics through weighted objectives, and the flexibility to incorporate complex fairness concepts as additional constraints without the need to redesign the entire algorithm. We conducted an extensive experimental analysis to demonstrate how F2Stories enables more fair or focus group-prioritized storyline visualizations while maintaining adherence to established layout constraints. Our evaluation includes comprehensive results from a detailed case study that shows the effectiveness of our approach in real-world narrative contexts. An open access copy of this paper and all supplemental materials are available at osf.io/e2qvy.

Motivated by the need for decision-making systems that avoid bias and discrimination, the concept of fairness recently gained traction in the broad field of artificial intelligence , stimulating new research also within the information visualization community. In this paper, we introduce a notion of fairness in network visualization, specifically for orthogonal and for straight-line drawings of graphs, two foundational paradigms in the field. We investigate the following research questions: (i) What is the price, in terms of global readability , of incorporating fairness constraints in graph drawings? (ii) How unfair is a graph drawing that does not optimize fairness as a primary objective ? We present both theoretical and empirical results. In particular, we design and implement two optimization algorithms for multi-objective functions, one based on an ILP model for orthogonal drawings, and one based on gradient descent for straight-line drawings. In a nutshell, we experimentally show that it is possible to significantly increase the fairness of a drawing by paying a relatively small amount in terms of reduced global readability. Also, we present a use case in which we qualitatively evaluate our approach on a practical scenario.

Edge bundling algorithms can significantly improve the visualization of dense graphs by identifying and bundling together suitable groups of edges and thus reducing visual clutter. As such, bundling is often viewed as a post-processing step applied to a drawing, and the vast majority of edge bundling algorithms consider a graph and its drawing as input. A different way of thinking about edge bundling is to simultaneously optimize both the drawing and the bundling, which we investigate in this paper. We build on an earlier work where we introduced a novel algorithmic framework for bundling-aware graph drawing consisting of three main steps, namely Filter for a skeleton subgraph, Draw the skeleton, and Bundle the remaining edges against the drawing of the skeleton. We propose several alternative implementations and experimentally compare them against each other and the simple idea of first drawing the full graph and subsequently applying edge bundling to it. The experiments confirm that bundled drawings created by our Filter-Draw-Bundle framework outperform previous approaches according to metrics for edge bundling and graph drawing.

Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an $st$-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source $s$ and a single sink $t$. Computing an $st$-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an $st$-orientation with at most $k$ transitive edges is more challenging and it was recently proven to be NP-hard already when $k=0$. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.

We study the parameterized complexity of the s-Club Cluster Edge Deletion (s-Club Cluster Vertex Deletion) problem: Given a graph G and two integers s≥2 and k≥1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-Club Cluster Edge Deletion and s-Club Cluster Vertex Deletion problems are known to be NP-hard already when s=2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-Club Cover, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d≥1 and s≥2.