区間最小値クエリを用いた SPQR-Tree の構築

合田 理貴

（指導教員：定兼 邦彦 教授／数理情報第2研究室）

研究概要

グラフの平面性判定を目的として考案された SPQR-Tree と呼ばれる構造は線形時間での構築アルゴリズムが知られているものの難解でアドホックな操作を含んでいた. 本研究では区間最小値クエリを用いて, より直観的な線形時間アルゴリズムを考案した.

グラフの SPQR-Tree の構築

卒論の感想

論文のサーベイから新手法の考案そして論文を完成させ, 発表と一連のプロセスを経験できたことは今後の研究生活での大きな自信になると思います.