文献

J-GLOBAL ID：201902231915653419   整理番号：19A2873183

平面グラフのためのユニバーサル点集合に関するノート【JST・京大機械翻訳】

A Note on Universal Point Sets for Planar Graphs

著者 (3件)： Scheucher Manfred (Institut fuer Mathematik, Technische Universitaet Berlin, Berlin, Germany) ,  Schrezenmaier Hendrik (Institut fuer Mathematik, Technische Universitaet Berlin, Berlin, Germany) ,  Steiner Raphael (Institut fuer Mathematik, Technische Universitaet Berlin, Berlin, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11904  ページ： 350-362  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 短報  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 平面点集合が固定数の頂点上のすべての平面グラフの同時直線埋込みを可能にすることを調べた。最初に,各n頂点平面グラフ(頂点が与えられた点として描かれる)の直線描画を見つけるために,少なくとも[数式:原文を参照]点が必要であることを示した。これにより,黒w(2004)による以前の最良の定数1.235を改善した。著者らの第二の主な結果は,徹底的な計算機探索に基づいている:著者らは,すべての平面11頂点グラフが同時に平面直線を描くことができる11点の集合が存在しないことを示した。これにより,主,Hoffmann,およびKusters(2015)による結果が強化され,[数式:原文を参照]頂点上のすべての平面グラフがn点の特定のn-普遍的集合上で同時に描かれるが,[数式:原文を参照]に対するn-普遍集合は存在しない。また,49の平面11頂点グラフを提供し,それらを11点の任意の集合上で同時に引き出すことができない。これは,事実上,問題の(負の)答えに対するもう一つのステップであり,2つの平面グラフを同時に描くことができる。Brass,Cenek,Duncan,EFRAT,Eren,Ismailescu,Kobourov,Lubw,およびMitchell(2007)によって提起される。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 計算機械 ,  *平面グラフ
準シソーラス用語： *点集合 , 【Automatic Indexing@JST】

著者キーワード (5件)： 同時埋め込み ,  積層三角測量 ,  順序型 ,  Boole充足可能性(SAT) ,  整数計画法(IP)

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 平面グラフ ,  点集合 ,  ノート