群馬大学理工学部

電子情報・数理教育プログラム博士前期課程1年の小島大輝君が、情報処理学会第80回全国大会で学生奨励賞を受賞しました。

 電子情報部門中野研究室の博士前期課程1年の小島大輝君が、2018年3月13日~15日に早稲田大学で開催された情報処理学会第80回全国大会で、学生奨励賞を受賞した。
 受賞題目は「k-外平面的グラフのangular resolution」であり、グラフ描画に関する研究である。グラフの見やすさの基準はいくつか考えられるが、一つの自然な基準として、描画に小さな角度が現れないものをよい描画と考え、最小角度をどの程度大きく保って描画できるかが研究されてきた。しかし、理論的限界として知られている角度と実際のアルゴリズムで達成できている角度の差が大きく、1990年代の研究以来、進展のない状態であった。今回、小島君は、三角形分割された2-外平面的グラフというグラフクラスに着目し、最小角度Ω(1/d^3)の描画法を与えることに成功した(dはグラフの最大次数)。この結果は、1990年代の外平面的グラフの描画法を大きく拡張したものであり、一般の平面的グラフの描画方法についても指針を与えるものである。さらに、発表後、最小角度Ω(1/d^2)での描画法の開発にも成功しており、今後もさらなる発展が期待できるものである。