Name
Abstract | ||
|---|---|---|
In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. 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)x (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 x 2n grid if T(G) has exactly four leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 6n x n(2) 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 polynomial size. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1587/transinf.E97.D.413 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
algorithm, convex grid drawing, graph drawing, plane graph, triconnected | Graph drawing,Combinatorics,Polyhedral graph,Convex hull,Steinitz's theorem,Geometry,Dominance drawing,1-planar graph,Medial graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
E97D | 3 | 1745-1361 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuyuki Miura | 1 | 0 | 0.68 |
| Kazuyuki Miura | 2 | 84 | 8.66 |