Evaluation of an Algorithm to Draw DAG Structure Used in the Thesaurus Browser `xthes'

DOI HANDLE Web Site Open Access
  • Ichimaru Natsuki
    Department of Intelligent Systems, Faculty of Information Science and Electrical Engineering, Kyushu University

Bibliographic Information

Other Title
  • シソーラスブラウザxthesにおけるDAG構造の描画アルゴリズムとその評価
  • シソーラスブラウザ xthes ニ オケル DAG コウゾウ ノ ビョウガ アルゴリズム ト ソノ ヒョウカ

Search this article

Description

In this paper, we present a method to plot a directed acyclic graph (DAG) which represents a hierarchical structure with multiple inheritances. This method is used in the thesaurus browser `xthes' to display 'is-a' relationship between nodes in a thesaurus or ontology. Because it is noted that the problem of minimizing arc crossings in a DAG is NP-hard, we need a fast heuristic algorithm. `xthes' draws a DAG as follows. At first, it splits a DAG into a tree and other non-tree arcs. Then, it rearranges the order of children nodes by clustering subtrees, and reverses the order of subtrees in the clusters, to make the length of inter-subtree links as short as possible. Finally, it minimizes the distance between subtrees in bottom-up manner, and decides the position of the nodes and arcs. By the experiment, it was confirmed that our node-exchanging method saves about 50% of the total length of the crossing arcs. It seems that our method can display a DAG in a comprehensible form, and that it is fast enough to update the diagram interactively.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top