平面上点集合の一様グリッドへの近似マッチング

• Item type: SIG Technical Reports(1)
• 公開日: 2012-08-02
• タイトル: 平面上点集合の一様グリッドへの近似マッチング
• タイトル / 言語: en
• タイトル: Efficient Grid Graph Layout by Approximate Point-set Matching on the Plane
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州工業大学大学院大学院情報工学研究院知能情報工学研究系
• 著者所属: 九州工業大学大学院情報工学研究院生命情報工学研究系
• 著者所属: 九州工業大学大学院情報工学研究院生命情報工学研究系バイオメディカルインフォマティクス研究開発センター
• 著者所属(英): en
• 著者所属(英): Dept. of A.I., Kyushu Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Dep. of Biosci. and Bioinfo., Kyushu Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Biomedical Informatics R&D Center, Kyushu Inst. of Tech.
• 著者名: 下薗真一; 井上, 健太郎; 倉田, 博之
• 著者名(英): Shinichi, Shimozono; Kentaro, Inoue; Hiroyuki, Kurata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 代謝ネットワークのような規模が大きい相関関係に対して，われわれはインタラクティブに利用できる程度に高速で，かつすべてのノードラベルを重なることなく描画できるグリッドグラフ描画法を提案している[3], [4], [5]．その中でもハイブリッドレイアウトアルゴリズム[3]は，自由に選んだグラフ描画法を前処理として利用可能である．分割統治的し格子点への近似点集合照合を行うもので，CADシステムに必要な高速性と，グリッド配置の前後での変化を予測しやすくしている．しかしこの近似点集合の照合は，一般の点集合どうしの照合を対象としたものであるため，時間計算量と領域計算量の次数が高く，分割は定数サイズとする必要があった．本稿では，この平面上の近似点集合照合アルゴリズムを格子点への照合に最適化したアルゴリズムを示す．このアルゴリズムは，配置対象のグリッド領域の大きさにかかわらず，ノード数nに関しO(n2)時間で動作する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present an O(n2)-time grid-layout algorithm for graphs with n nodes that aligns every node on lattice exclusively. The grid graph layout approach for biochemical network maps [3], [4], [5] is a graph drawing scheme that place nodes on sparse grid points to prevent overlaps of node labels. Hybrid grid layout algorithm presented in [3] combines an arbitrary graph layout method, which may cause label overlaps, and the algorithm that transforms an arbitrary graph into a grid graph, by the divide-and-conquer and an approximate point-set matching on the plane. Although the computational results shown that the algorithm is time-efficient and achieves appropriate node layout, its approximate point-set matching requires more than O(n6) time and thus the minimization of transformations could be applied only on small areas. In this paper, we show this can be improved as O(n2) time algorithm, by utilizing the uniformness of grid point space.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2012-BIO-30, 号 1, p. 1-3, 発行日 2012-08-02
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会