Drawing Order Diagrams Through Two-Dimension Extension
Vol. 27, no. 9, pp. 783-802, 2023. Regular paper.
Abstract Ordinal real-world data such as concept hierarchies, ontologies, genealogies, or task dependencies in scheduling often has the property to not only contain pairwise comparable, but also incomparable elements. Order diagrams provide an important tool for understanding and thus discovering knowledge in such data. Easily readable drawings of such order diagrams are hard to come by, even for small ordered sets. Many attempts were made to transfer classical graph drawing approaches to order diagrams. Although these methods produce satisfying results for some ordered sets, they unfortunately perform poorly in general. In this work, we present the novel algorithm DimDraw to decompose an ordered set (e.g., a concept hierarchy) in linear orders and to produce a corresponding order diagram. This algorithm is based on a relation between the dimension of an ordered set and the bipartiteness of its transitive incompatibility graph. To evaluate the quality of the algorithm, a user study was conducted where generated drawings were compared with ones from state-of-the-art drawing algorithms.

 This work is licensed under the terms of the CC-BY license.
Submitted: December 2022.
Reviewed: April 2023.
Revised: June 2023.
Accepted: November 2023.
Final: November 2023.
Published: December 2023.
Communicated by Csaba D. Tóth
article (PDF)