文献

J-GLOBAL ID：202202267265691673   整理番号：22A0495870

少数の勾配を持つレベル平面描画【JST・京大機械翻訳】

Level-Planar Drawings with Few Slopes

著者 (3件)： Brueckner Guido (Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany) ,  Krisam Nadine (Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany) ,  Mchedlidze Tamara (Utrecht University, Utrecht, Netherlands)
資料名： Algorithmica  (Algorithmica)
巻： 84  号： 1  ページ： 176-196  発行年： 2022年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 傾斜の固定数[数式:原文を参照]によるレベル平面直線描画を導入し,研究した。適切なレベルグラフ(すべてのエッジが隣接レベルの頂点を接続する)のために,著者らは,そのような描画を見つけるか,またはそのような描画が存在しないかを決定する[数式:原文を参照]-時間アルゴリズムを与えた。さらに,部分描画拡張問題を考察し,ここでは部分グラフの不変描画を全グラフの描画に拡張し,その共有部分グラフに対する制約が一致する2つのグラフの描画の存在に関する同時描画問題を検討した。適切なレベル平面グラフ上のこれらのそれぞれの問題に対する[数式:原文を参照]時間と[数式:原文を参照]時間アルゴリズムを示した。著者らは,[数式:原文を参照]傾斜による非プロペラレベルグラフアドミットレベル平面描画が制約された場合でさえNP困難であるかどうかを示すことにより,これらの肯定的結果を補完する。Copyright The Author(s) 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  平面グラフ ,  部分グラフ ,  NP困難
準シソーラス用語： 線画 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフ描画 ,  レベル平面性 ,  制約付き描画

分類 (2件)： グラフ理論基礎  (IA02020S) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (2件)： 勾配 ,  描画