IEICE TRANSACTIONS on Fundamentals
Grid Drawings of Five-Connected Plane Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1228-1234
- Publication Date
- 2022/09/01
- Publicized
- 2022/02/16
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2021DMP0010
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Graphs and Networks, Algorithms and Data Structures
Authors
Kazuyuki MIURA
Fukushima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
