文献

J-GLOBAL ID：202302282345225738   整理番号：23A3150168

グラフの閉曲面への埋め込み

著者 (1件)： 永並健吾 (成蹊大 理工)
資料名： オペレーションズ・リサーチ
巻： 68  号： 11  ページ： 563-570  発行年： 2023年11月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフは頂点集合と辺集合によって構成される組合せ的構造であるが,“点”と“線”からなる「図形」として表現することも多い.本稿ではそのようなグラフの幾何学的な側面に目を向ける.特に,平面やそれ以外の曲面に辺の交差なく描画されたグラフを扱っていく.(著者抄録)

シソーラス用語： *グラフ理論 ,  *平面グラフ ,  *閉曲面 ,  *位相幾何学 ,  *埋込み【写像】 ,  完全グラフ ,  無次元数 ,  等価性 ,  三角形分割 ,  環状体 ,  トーラス
準シソーラス用語： 種数

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (14件)：

• 野口健太,“平面グラフ・曲面上のグラフ,”オペレーションズ・リサーチ:経営の科学,61, pp. 832-836, 2016.
• C. Kuratowski, “Sur le problème des courbes gauches en topologie,”Fundamenta Mathematicae,15, pp. 271-283, 1930.
• J. Hopcroft and R. E. Tarjan, “Efficient planarity testing,” Journal of the Association for Computing Machinery, 21, pp. 549-568, 1974.
• C. Thomassen, “The graph genus problem is NPcomplete,”Journal of Algorithms, 10, pp. 568-576, 1989.
• B. Mohar, “A linear time algorithm for embedding graphs in an arbitrary surface,” SIAM Journal on Discrete Mathematics, 12, pp. 6-26, 1999.

タイトルに関連する用語 (3件)： グラフ ,  閉曲面 ,  埋め込み