Multidimensional Dominance Drawings

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, wG, 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 wG ≤ k ≤ fracn2. 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(n2wG) or O(n3) time, if we want k=wG. 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, wN, of a DAG G and we show how to improve the results given previously using these concepts.