TY - JOUR

T1 - Small grid drawings of planar graphs with balanced partition

AU - Zhou, Xiao

AU - Hikino, Takashi

AU - Nishizeki, Takao

N1 - Funding Information:
This work is supported in part by a Grant-in-Aid for Scientific Research (C) 19500001 from Japan Society for the Promotion of Science (JSPS).

PY - 2012/8

Y1 - 2012/8

N2 - 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 G1 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/3) 2n 2).

AB - 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 G1 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/3) 2n 2).

KW - Grid drawing

KW - Partition

KW - Planar graph

KW - Series-parallel graph

UR - http://www.scopus.com/inward/record.url?scp=84863715613&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863715613&partnerID=8YFLogxK

U2 - 10.1007/s10878-011-9381-7

DO - 10.1007/s10878-011-9381-7

M3 - Article

AN - SCOPUS:84863715613

SN - 1382-6905

VL - 24

SP - 99

EP - 115

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -