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 ×n grid if 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. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 2n ×n2 grid if T(G) has exactly four leaves. We also present an algorithm to find such a drawing in linear time. Our convex grid drawing has a rectangular contour, while most of the known algorithms produce grid drawings having triangular contours. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11940128_15 | ISAAC |
Keywords | DocType | Volume |
rectangular contour,triconnected component decomposition tree,plane graph g,n2 grid,grid drawing,grid point,triconnected plane graph,n grid,convex drawing,convex polygon,convex grid drawing,linear time,plane graph | Conference | 4288 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-49694-7 | 1 |
PageRank | References | Authors |
0.38 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akira Kamada | 1 | 4 | 0.81 |
| Kazuyuki Miura | 2 | 84 | 8.66 |
| Takao Nishizeki | 3 | 1771 | 267.08 |