Multidimensional Dominance Drawings
share
Let G be a DAG with n vertices and m edges. Two vertices u,v are incomparable if u doesn't reach v and vice versa. We denote by 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 < k <n/2. The time required by the algorithm is O(kn), with a precomputation time of O(km), needed to compute a 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.
READ FULL TEXT