# Multidimensional Dominance Drawings

arXiv: https://arxiv.org/abs/1906.09224 · HTML: https://mlsanity.com/paper/1906.09224/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [On the Learning and Learnability of Quasimetrics](https://mlsanity.com/paper/2206.15478/) (2022)

## Abstract (arXiv)

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.