Small grid drawings of planar graphs with balanced partition

• Published in: Journal of combinatorial optimization 2012-08, Vol.24 (2), p.99-115
• Main Authors: Zhou, Xiao, Hikino, Takashi, Nishizeki, Takao
• Format: Article
• Language: English
• Subjects: Applied sciences; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Convex and Discrete Geometry; Exact sciences and technology; Flows in networks. Combinatorial problems; Graph theory; Information retrieval. Graph; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operational research and scientific management; Operational research. Management science; Operations Research/Decision Theory; Optimization; Sciences and techniques of general use; Theoretical computing; Theory of Computation
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-011-9381-7

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 (4 n /3)×(2 n /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 (2 n /3)×(2 n /3) grid drawing and a grid drawing with area smaller than 0.3941 n 2 (