木構造図式の美的描画問題の研究および処理系の開発

我々は、フローチャートのようなプログラム流れ図を、より美しくより効率よく描画するための研究を行った。本研究では、木の描画問題に関する理論的研究をプログラム流れ図に応用し、与えられたプログラムを美しく流れ図に描画するための美的条件と、描画アルゴリズムについて考察した。与えられた美的条件を満足するようにグラフを描画する問題は、「美的描画問題」と呼ばれ、VLSIの配置問題等がよく知られている。我々は、プログラム流れ図に関する美的描画問題を、「木構造図式」と呼ばれる木の頂点に座標や頂点の大きさのなどの属性を持たせた木を与えられた美的条件を満たすように配置する問題として捕らえ、研究をおこなった。得られた結果を以下に列挙する。1.プログラム流れ図の描画を、木構造図式の美的描画問題の理論として体系化し数学的に表現した。2.木構造図式を美しく描画するための、美的条件を定式化した。3.上記美的条件を満たす配置を与える効率の良いアルゴリズム(O(n),O(n^2))を開発した。これらは、これまで木の美的描画問題で得られなかった効率の良いものである。4,上記2,3をもとに、美的条件の違いによる計算量の関係を明らかにした。5.上記3のアルゴリズムを取り入れたプログラム流れ図処理系をX-Windowsで開発した。

我々は、フローチャートのようなプログラム流れ図を、より美しくより効率よく描画するための研究を行った。本研究では、木の描画問題に関する理論的研究をプログラム流れ図に応用し、与えられたプログラムを美しく流れ図に描画するための美的条件と、描画アルゴリズムについて考察した。与えられた美的条件を満足するようにグラフを描画する問題は、「美的描画問題」と呼ばれ、VLSIの配置問題等がよく知られている。我々は、プログラム流れ図に関する美的描画問題を、「木構造図式」と呼ばれる木の頂点に座標や頂点の大きさのなどの属性を持たせた木を与えられた美的条件を満たすように配置する問題として捕らえ、研究をおこなった。得られた結果を以下に列挙する。1.プログラム流れ図の描画を、木構造図式の美的描画問題の理論として体系化し数学的に表現した。2.木構造図式を美しく描画するための、美的条件を定式化した。3.上記美的条件を満たす配置を与える効率の良いアルゴリズム(O(n),O(n^2))を開発した。これらは、これまで木の美的描画問題で得られなかった効率の良いものである。4,上記2,3をもとに、美的条件の違いによる計算量の関係を明らかにした。5.上記3のアルゴリズムを取り入れたプログラム流れ図処理系をX-Windowsで開発した。