A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We study the complexity of Rectilinear-Upward Planarity Testing and provide several algorithmic results. Precisely, we prove that: ( i ) the problem is NP-complete, even if G is biconnected; ( i i ) it can be solved in linear time when an upward planar embedding of G is fixed; ( i i i ) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; ( i v ) the problem is fixed-parameter tractable (namely, fixed-parameter linear) for all biconnected graphs, when parameterized by the number of sources and sinks in the digraph. • We study the algorithmic complexity of a problem that combines two well-established topics in graph drawing, namely rectilinear planar drawings and upward planar drawings. This problems, called rectilinear-upward planarity testing, asks to decide whether an input planar di-graph admits a planar drawing where each edge is either a horizontal or a vertical segment, and no edge points downwards. • We prove that rectilinear-upward planarity testing is NP-complete, even for biconnected digraphs. • We provide a linear-time algorithm for rectilinear-upward planarity testing of digraphs with a fixed upward planar embedding. • We provide a quadratic-time algorithm for rectilinear-upward planarity testing of biconnected partial 2-trees (i.e., digraphs whose underlying undirected graph is series-parallel) in the variable embedding setting. • We provide a fixed-parameter linear (FPL) algorithm for rectilinear- upward planarity testing of general biconnected digraphs in the variable embedding setting.

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

We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.

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 .

A weak dominance drawing Γ of a DAG G = ( V , E ) is a d -dimensional drawing such that D ( u ) < D ( v ) for every dimension D of Γ if there is a directed path from a vertex u to a vertex v in G , where D ( w ) is the coordinate of vertex w ∈ V in dimension D of Γ. If D ( u ) < D ( v ) for every dimension D of Γ, but there is no path from u to v , we have a falsely implied path (fip) . Minimizing the number of fips is an important theoretical and practical problem. Computing 2-dimensional weak dominance drawings with minimum number of fips is NP-hard. We show that this problem is FPT parameterized by the dimension d and the modular width mw . A key ingredient of our proof is the Compaction Lemma , where we show an interesting property of any weak dominance drawing of G with the minimum number of fips. This FPT result in weak dominance, which is interesting by itself because the fip-minimization problem is NP-hard, is used to prove our main contributions. Computing the dominance dimension of G , that is, the minimum number of dimensions d for which G has a d -dimensional dominance drawing (a weak dominance drawing with 0 fips), is a well-known NP-hard problem. We show that the dominance dimension of G is bounded by m w 2 (or mw , if m w < 4 ) and that computing the dominance dimension of G is an FPT problem with parameter mw . As far as we know, this the first FPT-algorithm to compute the dominance dimension of a DAG.

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.

Abstract A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term “plane” indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series–parallel graphs. Our linear-time algorithm is based on a characterization of the planar series–parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is “rolled-up” in an orthogonal drawing of the graph.

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.

This paper addresses a long standing, widely studied, open question: Given a planar 3-graph G (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of G in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of G the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing a linear-time algorithm that computes a bend-minimum planar orthogonal drawing of G. Also, if G is not K4, the drawing has at most one bend per edge. The existence of an orthogonal drawing Г of a planar 3-graph such that Г has the minimum number of bends and at most one bend per edge was previously unknown.