| 大会名称 |
|---|
| 2022年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2022 |
| 発行日 |
| 2022-08-30 |
| セッション番号 |
| 1a |
| セッション名 |
| アルゴリズム [選奨セッション] |
| 講演日 |
| 2022/09/13 |
| 講演場所(会議室等) |
| 12棟-101教室 |
| 講演番号 |
| CA-001 |
| タイトル |
| Convex Grid Drawings of Internally Triconnected Plane Graphs with Pentagonal Contours |
| 著者名 |
| 三浦一之, |
| キーワード |
| アルゴリズム, グラフ理論, 格子凸描画 |
| 抄録 |
|
In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on a 20n x 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n x 5n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. |
| 本文pdf |
| PDF download (841.3KB) |