Search

This paper discusses the hierarchical properties of digraphs and proposes flowchart decomposition algorithms using these properties. The hierarchical structure discussed here is based on only the topological relation- skips between vertices and the inclusive relationship among sets of vertices. When the given flowchart represents the control flow of a computer program, this hierarchical structure also shows strong correspondence between these inclusive relationships and program modules. The proposed flowchart decomposition algorithm consists of one algorithm for detecting modules and another algorithm for further decomposing the detected modules. This paper focuses on the former algorithm. Because the hierarchical structure discussed in this paper corresponds to the traditional program modules (e.g., function or procedure) of most of the computer programming languages, the module-detection algorithm can be used not only for decomposing flowchart but for more general purposes, including module design. Two types of module-detection algorithm are discussed in this paper. One detects all modules, and the other detects a restricted subset of modules from the standpoint of flow-chart decomposition. We then demonstrate with a practical example that the latter algorithm is ten times faster than the former. [ABSTRACT FROM AUTHOR]

A realizer of a triangulated plane graph G is a partition of interior edges of G, satisfying some conditions. The realizer has many applications, including graph drawing algorithms. Given a triangulated plane graph G, no algorithm to generate all realizers of G is known. In this paper, we first give an algorithm to generate all realizers. We first define a left canonical ordering for the vertices of an input graph, then show that there is a bijection between the left canonical orderings and realizers. Based on the bijection, we give an algorithm to generate all realizers. The algorithm generates each realizer in O(n) time without duplications, where n is the number of vertices in the graph. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(7): 40–47, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20276 [ABSTRACT FROM AUTHOR]

Various algorithms have been proposed for the problem of drawing rooted ordered trees. As one of them, Unno and colleagues [1] presented an O(n3) time algorithm that (1) produces an initial drawing of a given tree T, and then (2) finds a narrower drawing by repeatedly moving subtrees (n is the number of nodes in T). In this paper, we show that the same drawing can be obtained more efficiently by maintaining the contours of subtrees. If a natural restriction is imposed on the sizes of nodes, our method can be executed in a time O(n·α(n, n)), where α is a functional inverse of Ackermann's function. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(5): 31–41, 1997 [ABSTRACT FROM AUTHOR]