情報処理学会 第80回全国大会講演要旨

グラフを視覚的により理解しやすくするために、様々な基準の下で、グラフのよい描画を構成する研究が盛んになされている。その中でも、平面的グラフを辺を交差させずに角度をなるべく大きく描画する研究がある。既存研究として、平面的グラフを直線で辺の交差なく描画したとき最小角Ω(1/7^d)で描けることが知られている。しかし、より限定的なグラフではより角度を大きく描画できることが知られている。外平面的グラフは直線で辺の交差なく描画したとき最小角π/(d-1)で描けることが知られている。本研究では、外平面的グラフの一般化であるk-外平面的グラフのよい描画の理解に向けた第一歩として、2-外平面的グラフについて、最小角Ω(1/d²)となる描画法を与える。