pith. sign in

arxiv: 1906.09224 · v1 · pith:Z6UU42NMnew · submitted 2019-06-21 · 💻 cs.DS

Multidimensional Dominance Drawings

Giacomo Ortali (1) , Ioannis G. Tollis (2) ((1) University of Perugia , (2) Computer Science Department , University of Crete , Heraklion , Crete , Greece , Tom Sawyer Software
show 3 more authors
Inc. Berkeley CA U.S.A.)
This is my paper

Pith reviewed 2026-05-25 18:25 UTC · model grok-4.3

classification 💻 cs.DS
keywords dominance drawingdirected acyclic graphpartial order dimensiontransitive closuregraph drawing algorithmmultidimensional embeddingwidth of a poset
0
0 comments X

The pith

An algorithm computes a dominance drawing of any DAG in k dimensions where w_G ≤ k ≤ n/2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an algorithm that produces a dominance drawing of a directed acyclic graph in k dimensions, for any k satisfying the graph width w_G ≤ k ≤ n/2. The method runs in O(kn) time after an O(km) precomputation that builds a compressed transitive closure of the graph. When k equals the width, extra O(n² w_G) or O(n³) time may be needed. The construction yields a tighter upper bound on the dominance dimension of a DAG than earlier approaches. As direct consequences the work identifies a new family of graphs that admit two-dimensional dominance drawings and supplies a new upper bound on the dimension of any partial order. The paper also defines transitive modules and the dimensional neck w_N to refine the dimension results further.

Core claim

The central claim is an algorithm that, given a DAG G with n vertices and m edges, produces a dominance drawing in exactly k dimensions whenever w_G ≤ k ≤ n/2. The running time is O(kn) once a compressed transitive closure has been computed in O(km) time; achieving the minimal dimension k = w_G requires additional O(n² w_G) or O(n³) work. This supplies a stricter bound on the dominance dimension of G. Corollaries include a new infinite family of graphs possessing two-dimensional dominance drawings and a new upper bound on the dimension of an arbitrary partial order. The authors further introduce transitive modules and the dimensional neck w_N of G and demonstrate that these notions improve先前

What carries the argument

The compressed transitive closure of the DAG, which supports the construction of the k-dimensional dominance drawing after linear-time-per-dimension work.

If this is right

  • A new infinite family of graphs admits two-dimensional dominance drawings.
  • The dimension of any partial order satisfies a new, tighter upper bound.
  • Transitive modules and the dimensional neck w_N yield improved dimension bounds for some DAGs.
  • Dominance drawings become feasible for every DAG at any dimension between its width and n/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same precomputation technique could be reused to maintain dominance drawings under incremental edge insertions.
  • Transitive modules may simplify dimension calculations for other classes of poset representations beyond dominance drawings.
  • The O(kn) construction time suggests that interactive tools for exploring large partial orders could operate at interactive speeds once the closure is cached.

Load-bearing premise

A compressed transitive closure of the input DAG can be obtained in O(km) time for the chosen k.

What would settle it

A concrete DAG together with a value of k in [w_G, n/2] for which either no valid dominance drawing is produced or the observed running time exceeds the stated O(kn) bound.

Figures

Figures reproduced from arXiv: 1906.09224 by (2) Computer Science Department, CA, Crete, Giacomo Ortali (1), Greece, Heraklion, Inc. Berkeley, Ioannis G. Tollis (2) ((1) University of Perugia, Tom Sawyer Software, University of Crete, U.S.A.).

Figure 1
Figure 1. Figure 1: (a) An st-graph and a channel decomposition of it, with source 0 and sink 15. (b) A minimum size channel decomposition of G is Sc = {C1, C2, C3, C4}, where: C1 = {0, 1, 4, 5, 12, 13, 15}; C2 = {0, 3, 7, 11, 15}; C3 = {0, 2, 6, 10, 14, 15}; C4 = {0, 8, 9, 15}. 2.1 Minimum Size Channel Decomposition In this section we introduce the concept of width of an st-graph and we give a short description of an algorit… view at source ↗
Figure 2
Figure 2. Figure 2: Representation of the compressed transitive closure of graph G depicted in Fig￾ure 1(a) given the channel decomposition of it that is depicted in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of Algorithm 2D-Draw: (a) an st-graph G; (b) a two-channel de￾composition Sc = {C1, C2} of G, where: C1 = {0, 3, 4, 7}; C2 = {0, 1, 2, 5, 6, 7}; (c) the projections of the vertices of G on the channels they do not belong to; (d) the X coordinate assignment for the vertices of C1 and the Y coordinate assignment for the vertices of C2; (e) the assignment of the other coordinate of every vertex o… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of Algorithm kD-Draw on graph G depicted in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A dominance drawing with distinct coordinates obtained from the drawings shown in [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: (a) shows a transitive congruence partition CP = {M1, M2, M3, M4} of the graph G depicted in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: shows the graph obtained by adding a sink and a source to every module of the graph depicted in [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The induced graphs of graph G shown in [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The output of Algorithm Drawings-Computation given the set G(CP ) = {G0, G1, G2, G3, G4}, where G0 is depicted in [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of Algorithm Shifter using as input the drawings depicted in Fig￾ure 9: (a) shows the drawing Γ0; (b) shows Γ0 after the shifting done with respect to Γ1; (c) shows Γ0 after the shifting done with respect to Γ2; (d) shows Γ0 after the shifting done with respect to Γ3. The space reserved for Γ1, Γ2, and Γ3 during the algorithm is always shown with red boxes. 22 [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 1
Figure 1. Figure 1: Recall that G has a minimum size channel decomposition as shown in [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗
Figure 11
Figure 11. Figure 11: Output of Algorithm ND-Draw when the input is the set G(CP ) = {G0, G1, G2, G3, G4}, where G0 is depicted in [PITH_FULL_IMAGE:figures/full_fig_p024_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The drawing of [PITH_FULL_IMAGE:figures/full_fig_p025_12.png] view at source ↗
read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript presents an algorithm that computes a k-dimensional dominance drawing of a DAG G (w_G ≤ k ≤ n/2) in O(kn) time after O(km) precomputation to obtain a compressed transitive closure of G. It introduces the notions of transitive module and dimensional neck w_N, claims a tighter bound on dominance dimension, and derives corollaries including a new family of graphs admitting 2-dimensional dominance drawings and a new upper bound on the dimension of a partial order.

Significance. If the stated time bounds and the O(km) compressed-transitive-closure subroutine are correct, the work would supply a concrete construction for dominance drawings in a controllable number of dimensions together with new structural parameters (transitive modules, w_N) that improve prior dimension bounds.

major comments (1)
  1. [Abstract] Abstract (and the algorithm description): the headline complexity O(kn) + O(km) rests on the claim that a compressed transitive closure can be computed in O(km) time for arbitrary DAGs and any chosen k in [w_G, n/2]. No algorithm, reduction, or citation establishing this bound is supplied; standard transitive-closure algorithms are Ω(nm) (or faster only via matrix multiplication, which does not obviously produce an O(km) compressed form). This step is load-bearing for the central runtime claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting the central complexity claim. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the algorithm description): the headline complexity O(kn) + O(km) rests on the claim that a compressed transitive closure can be computed in O(km) time for arbitrary DAGs and any chosen k in [w_G, n/2]. No algorithm, reduction, or citation establishing this bound is supplied; standard transitive-closure algorithms are Ω(nm) (or faster only via matrix multiplication, which does not obviously produce an O(km) compressed form). This step is load-bearing for the central runtime claim.

    Authors: We agree that the manuscript does not supply an algorithm, reduction, or citation establishing an O(km) bound for the compressed transitive closure on arbitrary DAGs. Standard transitive closure is indeed Ω(nm) in the worst case, and the compressed form does not obviously inherit an O(km) bound for arbitrary k. This is a substantive gap in the current presentation. In the revision we will either (a) insert a self-contained subroutine (or citation) achieving O(km) time for the required compressed representation when k ≥ w_G, or (b) replace the O(km) claim with the best rigorously supported bound and adjust all stated running times accordingly. The remainder of the dominance-drawing construction and the new structural parameters (transitive modules, dimensional neck) are independent of this precomputation detail and will be retained. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithm claims derive from explicit construction steps

full rationale

The paper states an algorithm that produces a k-dimensional dominance drawing for w_G ≤ k ≤ n/2 with time O(kn) after O(km) precomputation of a compressed transitive closure. No quoted step defines the output dimension, width bound, or runtime in terms of the result itself, nor renames a fitted quantity as a prediction. No self-citation is shown to be the sole load-bearing justification for the core claims, and the derivation is presented as an explicit algorithmic procedure rather than a tautology or redefinition of inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 2 invented entities

Review performed on abstract only; full text unavailable, so free parameters, axioms, and invented entities cannot be exhaustively audited. The abstract introduces two new concepts that function as invented entities.

invented entities (2)
  • transitive module no independent evidence
    purpose: Improve results on dominance drawings
    New concept introduced to tighten previous bounds
  • dimensional neck w_N no independent evidence
    purpose: Measure to improve algorithm results
    New measure defined for DAGs

pith-pipeline@v0.9.0 · 5793 in / 1219 out tokens · 35392 ms · 2026-05-25T18:25:49.622263+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    K. P. Bogart. Maximal dimensional partially ordered sets i. hiraguchi’s theo- rem. Discrete Mathematics, 5(1):21–31, 1973. URL: https://doi.org/10.1016/ 0012-365X(73)90024-1, doi:10.1016/0012-365X(73)90024-1

    work page doi:10.1016/0012-365x(73)90024-1 1973

  2. [2]

    Chen and Y

    Y. Chen and Y. Chen. On the dag decomposition.British Journal of Mathematics and Computer Science, 2014. 10(6): 1-27, 2015, Article no.BJMCS.19380, ISSN: 2231-0851

    work page 2014

  3. [3]

    Di Battista, P

    G. Di Battista, P. Eades, R. Tamassia, and I. Tollis.Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1998. pp. 112–127

    work page 1998

  4. [4]

    Di Battista, R

    G. Di Battista, R. Tamassia, and I. G. Tollis. Area requirement and symmetry dis- play of planar upward drawings.Discrete & Computational Geometry, 7:381–401,

    work page

  5. [5]

    URL: https://doi.org/10.1007/BF02187850, doi:10.1007/BF02187850

    work page doi:10.1007/bf02187850

  6. [6]

    R. P. Dilworth. A decomposition theorem for partially ordered sets. ann. math. 52, (1950), 161-166

    work page 1950

  7. [7]

    Y. A. Dinitz. Algorithm for solution of a problem of maximum flow in networks with power estimation.Soviet Math. Doklady, 11:1277–1280, 1970. URL: https: //ci.nii.ac.jp/naid/10021311931/en/

    work page arXiv 1970

  8. [8]

    H. A. ElGindy, M. E. Houle, W. Lenhart, M. Miller, D. Rappaport, and S. White- sides. Dominance drawings of bipartite graphs. InProceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, August 1993, pages 187–191, 1993

    work page 1993

  9. [9]

    Hiraguchi

    T. Hiraguchi. On the dimension of partially ordered sets. Sci. Rep. Kanazawa Univ., pages 77–94, 1951

    work page 1951

  10. [10]

    H. V. Jagadish. A compression technique to materialize transitive closure.ACM Trans. Database Syst., 15(4):558–598, 1990. URL:http://doi.acm.org/10.1145/ 99935.99944, doi:10.1145/99935.99944

    work page doi:10.1145/99935.99944 1990

  11. [11]

    E. M. Kornaropoulos and I. G. Tollis. Weak dominance drawings and linear exten- sion diameter. CoRR, abs/1108.1439, 2011. URL:http://arxiv.org/abs/1108. 1439, arXiv:1108.1439

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  12. [12]

    E. M. Kornaropoulos and I. G. Tollis. Weak dominance drawings for directed acyclic graphs. In Graph Drawing - 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, pages 559–560, 2012. URL: https://doi.org/10.1007/978-3-642-36763-2_52, doi: 10.1007/978-3-642-36763-2\_52

    work page doi:10.1007/978-3-642-36763-2_52 2012

  13. [13]

    E. M. Kornaropoulos and I. G. Tollis. Algorithms for overloaded orthogonal draw- ings. J. Graph Algorithms Appl., 20(2):217–246, 2016. URL: https://doi.org/ 10.7155/jgaa.00391, doi:10.7155/jgaa.00391

    work page doi:10.7155/jgaa.00391 2016

  14. [14]

    L. Li, W. Hua, and X. Zhou. HD-GDD: high dimensional graph domi- nance drawing approach for reachability query. World Wide Web, 20(4):677– 696, 2017. URL: https://doi.org/10.1007/s11280-016-0407-z, doi:10.1007/ s11280-016-0407-z

    work page doi:10.1007/s11280-016-0407-z 2017

  15. [15]

    R. M. McConnell and F. de Montgolfier. Linear-time modular decomposition of di- rected graphs.Discrete Applied Mathematics, 145(2):198–209, 2005. URL:https: //doi.org/10.1016/j.dam.2004.02.017, doi:10.1016/j.dam.2004.02.017

    work page doi:10.1016/j.dam.2004.02.017 2005

  16. [16]

    R. M. McConnell and J. Spinrad. Linear-time transitive orientation.SODA, pages 19–25, 1997

    work page 1997

  17. [17]

    R. M. McConnell and J. P. Spinrad. Modular decomposition and transitive orien- tation. Discrete Mathematics, 201(1-3):189–241, 1999. URL: https://doi.org/ 10.1016/S0012-365X(98)00319-7, doi:10.1016/S0012-365X(98)00319-7. 28

    work page doi:10.1016/s0012-365x(98)00319-7 1999

  18. [18]

    J. M. Six and I. G. Tollis. Automated visualization of process diagrams. In P. Mutzel, M. Jünger, and S. Leipert, editors,Graph Drawing, pages 45–59, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg

    work page 2002

  19. [19]

    R. R. Veloso, L. Cerf, W. M. Jr., and M. J. Zaki. Reachability queries in very large graphs: A fast refined online search approach. In Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014., pages 511–522, 2014. URL: https://doi.org/10. 5441/002/edbt.2014.46, doi:10.5441/002/edbt.2014.46

    work page doi:10.5441/002/edbt.2014.46 2014

  20. [20]

    Yannakakis

    M. Yannakakis. The complexity of the partial order dimension problem.SIAM J. Algebraic and Discrete Methods, 3:303–322, 1982

    work page 1982

  21. [21]

    J. Zhou, S. Zhou, J. X. Yu, H. Wei, Z. Chen, and X. Tang. Dag reduction: Fast answering reachability queries. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD ’17, pages 375–390, New York, NY, USA, 2017. ACM. URL: http://doi.acm.org/10.1145/3035918.3035927, doi:10.1145/3035918.3035927. 29

    work page doi:10.1145/3035918.3035927 2017