頂点分割によるグラフの平面化とその描画【JST・京大機械翻訳】

Nollenburg Martin; Sorge Manuel; Terziadis Soeren; Villedieu Anaies; Wu Hsiang-Yun; Wulms Jules

プレプリント

J-GLOBAL ID：202202214664317960 整理番号：22P0294905

頂点分割によるグラフの平面化とその描画【JST・京大機械翻訳】

Planarizing Graphs and their Drawings by Vertex Splitting

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (6件)： , , , , ,
資料名：
発行年： 2022年02月24日プレプリントサーバーでの情報更新日： 2022年09月08日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフG=(V,E)の分割数は,頂点分割が頂点v∈Vを削除し,2つの新しい頂点v_1,v_2を導入し,その2つの分裂コピーv_1,v_2間のvに先入するエッジを分布させる,平面グラフにGを変換するために必要な頂点分割の最小数である。分割数問題はNP完全であることが知られている。本論文では,頂点分割から生じる新しい頂点を残りのグラフの既存の描画に再埋め込むことができるR ̄2におけるグラフ描画の分割数に焦点を当てた。最初に,分割数問題(描画なし)のための非一様固定パラメータ扱いやすい(FPT)アルゴリズムを提供した。次に,グラフ描画に対する分割数問題のNP完全性を示し,(1)頂点の最小部分集合を分割し,(2)与えられた頂点集合の最小数を再埋込みする。後者の問題のために,頂点分割の数によってパラメータ化されたFPTアルゴリズムを提示する。このアルゴリズムは有界外平面性ケースに縮小し,球カット分解に関する複雑な動的プログラムを使用する。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

グラフ理論基礎

, ,

前のページに戻る