Drawing Order Diagrams Through Two-Dimension Extension

Authors

  • Dominik Dürrschnabel
  • Tom Hanika
  • Gerd Stumme

DOI:

https://doi.org/10.7155/jgaa.00645

Keywords:

Knowledge Discovery , Concept hierarchies , Ordered Sets , Order Diagrams , Lattices

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.

Downloads

Download data is not yet available.

Downloads

Published

2024-03-16

How to Cite

Dürrschnabel, D., Hanika, T., & Stumme, G. (2024). Drawing Order Diagrams Through Two-Dimension Extension. Journal of Graph Algorithms and Applications, 27(9), 783–802. https://doi.org/10.7155/jgaa.00645

Issue

Section

Articles

Categories