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
Un dessin en grille d'un graphique plan G est un dessin de G sur le plan de sorte que tous les sommets de G sont placés sur des points de grille plane et toutes les arêtes sont dessinées sous forme de segments de ligne droite entre leurs extrémités sans aucune intersection d'arête. Dans cet article, nous donnons un algorithme en temps linéaire pour trouver un dessin de grille d'un graphe plan à 5 connexions donné. G avec cinq sommets ou plus sur la face extérieure. La taille du dessin satisfait W + H≤n - 2, où n est le nombre de sommets dans G, W est la largeur et H est la hauteur du dessin de la grille.
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.
Copier
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
Copier
@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},}
Copier
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 -