The search functionality is under construction.
The search functionality is under construction.

Convex Grid Drawings of Plane Graphs with Pentagonal Contours on O(n2) Grids

Kei SATO, Kazuyuki MIURA

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1142-1149
Publication Date
2021/09/01
Publicized
2021/03/10
Online ISSN
1745-1337
DOI
10.1587/transfun.2020DMP0011
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Graphs and Networks

Authors

Kei SATO
  Fukushima University
Kazuyuki MIURA
  Fukushima University

Keyword