Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPlacing Arrows in Directed Graph Drawings
108
0
0.0
(
0
)
Added by
Carla Binucci
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study.
rate research
Read More
A new efficient algorithm is presented for finding all simple cycles that satisfy a length constraint in a directed graph. When the number of vertices is non-trivial, most cycle-finding problems are of practical interest for sparse graphs only. We show that for a class of sparse graphs in which the vertex degrees are almost uniform, our algorithm can find all cycles of length less than or equal to $k$ in $O((c+n)(k-1)d^k)$ steps, where $n$ is the number of vertices, $c$ is the total number of cycles discovered, $d$ is the average degree of the graphs vertices, and $k > 1$. While our analysis for the running time addresses only a class of sparse graphs, we provide empirical and experimental evidence of the efficiency of the algorithm for general sparse graphs. This algorithm is a significant improvement over the only other deterministic algorithm for this problem known to us; it also lends itself to massive parallelism. Experimental results of a serial implementation on some large real-world graphs are presented.
Let $G$ be a DAG with $n$ vertices and $m$ edges. Two vertices $u,v$ are incomparable if $u$ doesnt reach $v$ and vice versa. We denote by emph{width} of a DAG $G$, $w_G$, the maximum size of a set of incomparable vertices of $G$. In this paper we present an algorithm that computes a dominance drawing of a DAG G in $k$ dimensions, where $w_G le k le frac{n}{2}$. The time required by the algorithm is $O(kn)$, with a precomputation time of $O(km)$, needed to compute a emph{compressed transitive closure} of $G$, and extra $O(n^2w_G)$ or $O(n^3)$ time, if we want $k=w_G$. Our algorithm gives a tighter bound to the dominance dimension of a DAG. As corollaries, a new family of graphs having a 2-dimensional dominance drawing and a new upper bound to the dimension of a partial order are obtained. We also introduce the concept of transitive module and dimensional neck, $w_N$, of a DAG $G$ and we show how to improve the results given previously using these concepts.
The emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in combinatorial geometry. We consider the distance-number of trees, graphs with no $K^-_4$-minor, complete bipartite graphs, complete graphs, and cartesian products. Our main results concern the distance-number of graphs with bounded degree. We prove that $n$-vertex graphs with bounded maximum degree and bounded treewidth have distance-number in $mathcal{O}(log n)$. To conclude such a logarithmic upper bound, both the degree and the treewidth need to be bounded. In particular, we construct graphs with treewidth 2 and polynomial distance-number. Similarly, we prove that there exist graphs with maximum degree 5 and arbitrarily large distance-number. Moreover, as $Delta$ increases the existential lower bound on the distance-number of $Delta$-regular graphs tends to $Omega(n^{0.864138})$.
The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths covering all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of $D,$ there is at least one arc between $x$ and $y.$ viol{Thus, a tournament is a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC) problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and $ell$, we are to decide whether there is a subset $X$ of $V$ of size $k$ such that the largest strong connectivity component in $D-X$ has at most $ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, ell,ell+k$ and $n-ell$. In particular, we prove that DCOC with parameter $k$ on semicomplete digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$ unless the Exponential Time Hypothesis (ETH) fails. gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-ell)})$ for the parameter $n-ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-ell})})$ unless ETH fails.} Finally, we improve viol{(in dependency on $ell$)} the upper bound of G{{o}}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $ell+k$ on general digraphs from $O^*(2^{O(kelllog (kell))})$ to $O^*(2^{O(klog (kell))}).$ Note that Drange, Dregi and van t Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time $O^*(2^{o(klog ell)})$ unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity $O^*(2^{o(klog k)}).$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
