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

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-22
• タイトル: グラフの平面への直線埋込み問題
• タイトル / 言語: en
• タイトル: Straight - line embeddings of rooted forests in the plane
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 茨城大学
• 著者所属: 工学院大学
• 著者所属: 東京医科歯科大学
• 著者所属(英): en
• 著者所属(英): Ibaraki University
• 著者所属(英): en
• 著者所属(英): Kogakuin University
• 著者所属(英): en
• 著者所属(英): Tokyo Medical and Dental University
• 著者名: 加納, 幹雄; 金子, 篤司; 徳永, 伸一
• 著者名(英): Mikio, Kano; Atsushi, Kaneko; Shin-Ichi, Tokunaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの直線埋込みとは、グラフを平面上に各辺が直線分でかつ交差しないように描くことである。ここではグラフの点集合となる平面上の点集合が指定されており、さらにグラフのいくつかの特別な点は、その対応する点が指定されているような場合の直線埋込みを考える。具体的には、互いに素なn個の根付き木T_1，T_2 ．．．，T_nの和グラフF：＝T_1∪T_2∪・・・∪T_nを、指定された人個の点p1，p2，．．．，pnを含む｜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｜である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let F:=T_1∪T_2∪…∪T_k be a rooted forest with roots v_1, v_2, ..., v_k and let P be a set of ｜F｜points in the plane in general position containing n specified points p_1, p_2, ..., P_k. We say that F can be strongly (or weakly) stright-line embedded onto P if F can be embedded in the plane so that every vertex of F corresponds to a point of P, every edge corresponds to a straight-line segment, no two straight-line segments intersect except their common end-point, and so that the root v_i corresponds to p_i for every 1〓i〓k (or the set{v_1, ..., v_k}of roots corresponds to the Set ｛P1, ..., P_k｝of specified points}. We give some results on stronlgy and weakly stright-line embeddeing of rooted forests.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 62(1998-AL-063), p. 1-8, 発行日 1998-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会