| Item type |
SIG Technical Reports(1) |
| 公開日 |
2017-05-05 |
| タイトル |
|
|
タイトル |
Acute Constrains in Straight-Line Drawings of Planar Graphs |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Acute Constrains in Straight-Line Drawings of Planar Graphs |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
京都大学情報学研究科数理工学専攻 |
| 著者所属 |
|
|
|
京都大学情報学研究科数理工学専攻 |
| 著者所属 |
|
|
|
京都大学情報学研究科数理工学専攻 |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 著者名 |
瀬戸, 明嶺
シュルベフスキ, アレクサンダル
永持, 仁
|
| 著者名(英) |
Akane, Seto
Aleksandar, Shurbevski
Hiroshi, Nagamochi
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Recent research on graph drawing focuses on Right-Angle-Crossing (RAG) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O (n²) - time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Recent research on graph drawing focuses on Right-Angle-Crossing (RAG) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O (n²) - time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2017-AL-163,
号 8,
p. 1-8,
発行日 2017-05-05
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL17163008.pdf (1.1 MB)
