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 is known that every planar graph G of n vertices has a grid drawing on an (n驴2)脳(n驴2) or (4n/3)脳(2n/3) integer grid. In this paper we show that if a planar graph G has a balanced partition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G 1 and G 2, then G has a max驴{n 1,n 2}脳max驴{n 1,n 2} grid drawing, where n 1 and n 2 are the numbers of vertices in G 1 and G 2, respectively. In particular, we show that every series-parallel graph G has a (2n/3)脳(2n/3) grid drawing and a grid drawing with area smaller than 0.3941n 2 (2 n 2). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10878-011-9381-7 | J. Comb. Optim. |
Keywords | Field | DocType |
Grid drawing,Planar graph,Series-parallel graph,Partition | Discrete mathematics,Outerplanar graph,Combinatorics,Graph power,Slope number,Bound graph,Planar straight-line graph,Cycle graph,Graph bandwidth,Dominance drawing,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 2 | 1382-6905 |
Citations | PageRank | References |
2 | 0.36 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiao Zhou | 1 | 325 | 43.69 |
| Takashi Hikino | 2 | 4 | 0.75 |
| Takao Nishizeki | 3 | 1771 | 267.08 |