The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dalam lukisan grid cembung graf satah, semua tepi dilukis sebagai segmen garis lurus tanpa sebarang persilangan tepi, semua bucu diletakkan pada titik grid dan semua kitaran muka dilukis sebagai poligon cembung. Graf satah G mempunyai lukisan cembung jika dan hanya jika G disambung tiga secara dalaman, dan graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada (n-1)×(n-1) grid jika sama ada G adalah bersambung tiga atau pokok penguraian komponen bersambung tiga T(G) daripada G mempunyai dua atau tiga daun, di mana n ialah bilangan bucu dalam G. Graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 2n× 2n grid jika T(G) mempunyai tepat empat daun. Tambahan pula, graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 6n×n2 grid jika T(G) mempunyai tepat lima daun. Dalam makalah ini, kami menunjukkan bahawa graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 20n× 16n grid jika T(G) mempunyai tepat lima daun. Kami juga membentangkan algoritma untuk mencari lukisan sedemikian dalam masa linear. Ini ialah algoritma pertama yang menemui lukisan grid cembung bagi graf satah sedemikian G dalam grid O(n2) saiz.
Kei SATO
Fukushima University
Kazuyuki MIURA
Fukushima University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Kei SATO, Kazuyuki MIURA, "Convex Grid Drawings of Plane Graphs with Pentagonal Contours on O(n2) Grids" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1142-1149, September 2021, doi: 10.1587/transfun.2020DMP0011.
Abstract: 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 an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 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 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0011/_p
Salinan
@ARTICLE{e104-a_9_1142,
author={Kei SATO, Kazuyuki MIURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Convex Grid Drawings of Plane Graphs with Pentagonal Contours on O(n2) Grids},
year={2021},
volume={E104-A},
number={9},
pages={1142-1149},
abstract={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 an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 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 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.},
keywords={},
doi={10.1587/transfun.2020DMP0011},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - Convex Grid Drawings of Plane Graphs with Pentagonal Contours on O(n2) Grids
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1142
EP - 1149
AU - Kei SATO
AU - Kazuyuki MIURA
PY - 2021
DO - 10.1587/transfun.2020DMP0011
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2021
AB - 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 an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 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 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.
ER -