グラフの平面への直線埋込み問題

概要

論文の詳細を見る
グラフの直線埋込みとは、グラフを平面上に各辺が直線分でかつ交差しないように描くことである。ここではグラフの点集合となる平面上の点集合が指定されており、さらにグラフのいくつかの特別な点は、その対応する点が指定されているような場合の直線埋込みを考える。具体的には、互いに素なn個の根付き木T_1, T_2, ..., T_nの和グラフF:=T_1∪T_2∪・・・∪T_nを、指定されたn個の点p_1, p_2, ..., p_nを含む|F|個の点からなる平面上の点集合P上に直線埋込みする問題を考える。このとき、各根付き木T_i, 1≤i≤n, の根v_iは、指定された点p_iに対応させるものとする。またこの根の対応条件を、根の集合{v_1, v_2, ..., v_n}は全体として指定された点の集合{p_1, p_2, ...p_n}に対応するものと条件を弱めた直接埋込みも考える。特に、3個の根付き木の和T_∪T_2∪T_3には、前の意味での直線埋込みのできない点集合と根付き木が存在することを示し、かつ後の意味で直接埋込みできることをしめす。また証明から、このような埋込みがO(N^2logN)時間で実現できるアルゴリズムも得られる。ただしN=|T_1∪T_2∪T_3|である。
一般社団法人情報処理学会の論文
1998-07-22