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
Um desenho de grade de um gráfico plano G é um desenho de G no plano de modo que todos os vértices de G são colocados em pontos de grade plana e todas as arestas são desenhadas como segmentos de linha reta entre seus pontos finais, sem qualquer interseção de arestas. Neste artigo, fornecemos um algoritmo de tempo linear para encontrar um desenho de grade de qualquer grafo plano 5 conectado. G com cinco ou mais vértices na face externa. O tamanho do desenho satisfaz W + H≤n - 2, onde n é o número de vértices em G, W é a largura e H é a altura do desenho da grade.
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.
Copiar
Kazuyuki MIURA, "Grid Drawings of Five-Connected Plane Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1228-1234, September 2022, doi: 10.1587/transfun.2021DMP0010.
Abstract: A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0010/_p
Copiar
@ARTICLE{e105-a_9_1228,
author={Kazuyuki MIURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Grid Drawings of Five-Connected Plane Graphs},
year={2022},
volume={E105-A},
number={9},
pages={1228-1234},
abstract={A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.},
keywords={},
doi={10.1587/transfun.2021DMP0010},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - Grid Drawings of Five-Connected Plane Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1228
EP - 1234
AU - Kazuyuki MIURA
PY - 2022
DO - 10.1587/transfun.2021DMP0010
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.
ER -