Name
Abstract | ||
|---|---|---|
In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It has been known that every planar graph G of n vertices has a grid drawing on an (n−2)×(n−2) integer grid and such a drawing can be found in linear time. In this paper we show that if a planar graph G has a balanced bipartition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G1 and G2, then G has a grid drawing on a W×H grid such that both the width W and height H are smaller than the larger number of vertices in G1 and in G2. In particular, we show that every series-parallel graph G has a grid drawing on a (2n/3)×(2n/3) grid and such a drawing can be found in linear time. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-11440-3_5 | WALCOM |
Keywords | Field | DocType |
small grid drawing,height h,integer grid,grid drawing,grid point,planar graph,small grid area,series-parallel graph,linear time,width w,h grid,balanced bipartition | Discrete mathematics,Outerplanar graph,Combinatorics,Graph power,Slope number,Planar straight-line graph,Book embedding,Dominance drawing,Lattice graph,Mathematics,Planar graph | Conference |
Volume | ISSN | ISBN |
5942 | 0302-9743 | 3-642-11439-3 |
Citations | PageRank | References |
2 | 0.39 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiao Zhou | 1 | 325 | 43.69 |
| Takashi Hikino | 2 | 4 | 0.75 |
| Takao Nishizeki | 3 | 1771 | 267.08 |