- 著者
-
吉井 訓史
中野 眞一
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. A, 基礎・境界 (ISSN:09135707)
- 巻号頁・発行日
- vol.88, no.8, pp.945-952, 2005-08-01
- 被引用文献数
-
9
グラフを, 各面が方形(長方形)であるように, かつ, 辺が交差することなく平面に描画したものを, 方形描画と呼ぶ. 内面の個数がたかだかn個であるすべての方形描画を, 重複も抜けもなく高速に列挙するアルゴリズムが知られている. 本論文では, この列挙アルゴリズムを改造することにより, 方形描画を列挙することなく, これらの個数のみを高速に数え上げるアルゴリズムを提案する. また, この数え上げアルゴリズムを実装することにより, 方形描画の個数の値をn≤13について求めた. 更に, 従来の列挙アルゴリズムも実装し, 方形描画の個数の値を求めた. 方形描画の個数は, 上記二つの結果において一致することを確認した. これにより, これまで未解決であった方形描画の個数の値がn≤13まで新たに確定した. 今回提案する数え上げアルゴリズムは, 従来の列挙アルゴリズムより約200倍高速であった.