著者

吉井 訓史 中野 眞一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. A, 基礎・境界 (ISSN:09135707)

巻号頁・発行日

vol.88, no.8, pp.945-952, 2005-08-01

被引用文献数

9

---

グラフを, 各面が方形(長方形)であるように, かつ, 辺が交差することなく平面に描画したものを, 方形描画と呼ぶ. 内面の個数がたかだかn個であるすべての方形描画を, 重複も抜けもなく高速に列挙するアルゴリズムが知られている. 本論文では, この列挙アルゴリズムを改造することにより, 方形描画を列挙することなく, これらの個数のみを高速に数え上げるアルゴリズムを提案する. また, この数え上げアルゴリズムを実装することにより, 方形描画の個数の値をn≤13について求めた. 更に, 従来の列挙アルゴリズムも実装し, 方形描画の個数の値を求めた. 方形描画の個数は, 上記二つの結果において一致することを確認した. これにより, これまで未解決であった方形描画の個数の値がn≤13まで新たに確定した. 今回提案する数え上げアルゴリズムは, 従来の列挙アルゴリズムより約200倍高速であった.