Abstract We introduce C lusterix , a novel hybrid visualization model for representing hierarchically clustered networks, which also supports directed and weighted edges. C lusterix offers an integrated view of both the network and its full cluster hierarchy by compactly visualizing the cluster inclusion tree enriched with links of the network. This is achieved through matrix‐based representations at various hierarchy levels, combined with a node‐link style linear layout at the leaf level. To support layout computation based on C lusterix , we propose two algorithmic approaches: an exact Integer Linear Program and a fast heuristic, both aimed at minimizing edge crossings. We present an extensive experimental comparison of these algorithmic approaches to highlight the trade‐offs between efficiency and effectiveness. Moreover, as a proof of concept for our model, we developed an interactive visualization system based on C lusterix and evaluated its performance through case studies and qualitative feedback from experts in different application domains.

• 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 .

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.

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.

Abstract A map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at mostknations touch at the same point is ak-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for anyk, if the input graph admits ak-map or a hole-free k-map.

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.

We study the complexity of testing whether a biconnected graph G=(V,E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D(v) of FPQ-trees. Let tw be the treewidth of G and let Dmax be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw+Dmax, paraNP-hard when parameterized by Dmax, and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected.

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.

Many real-world networks are globally sparse but locally dense. Typical examples are social networks, biological networks, and information networks. This double structural nature makes it difficult to adopt a homogeneous visualization model that clearly conveys both an overview of the network and the internal structure of its communities at the same time. As a consequence, the use of hybrid visualizations has been proposed. For instance, NodeTrix combines node-link and matrix-based representations (Henry et al., 2007). In this article we describe ChordLink, a hybrid visualization model that embeds chord diagrams, used to represent dense subgraphs, into a node-link diagram, which shows the global network structure. The visualization makes it possible to interactively highlight the structure of a community while keeping the rest of the layout stable. We discuss the intriguing algorithmic challenges behind the ChordLink model, present a prototype system that implements it, and illustrate case studies on real-world networks.

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$.