## Dept. of CS Seminar Small Grid Drawings 12/21

D E P A R T M E N T O F C O M P U T E R S C I E N C E

Distinguished Lecture Series

Topic: Small Grid Drawings of Planar Graphs with Balanced Bipartition

Presented By: Takao Nishizeki, Dean and Professor

From: Graduate School of Information Sciences, Tohoku University, Japan

Biography: Professor Takao Nishizeki, currently Dean and Professor of algorithm theory in the Graduate School of Information Sciences, Tohoku University in Japan, was born in Fukushima, northeastern part of Japan, in 1947. He received the B. E., M. E. and D. E. degrees in electrical communication engineering from Tohoku University, one of the most prominent universities in Japan, in 1969, 1971 and 1974, respectively. Upon graduation, he joined the faculty at Tohoku University, where in 1988 he was appointed to the current professorship.

Date: Monday, December 21, 2009

Time: 2:00 p.m. – 3:00 p.m.

Location: Engineering and Computer Science Building (ECS), Room # 660

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)x(n-2) integer grid and such a drawing can be found in linear time. In this talk, 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 G_1 and G_2, then G has a grid drawing on a WxH grid such that both the width W and height H are smaller than the larger number of vertices in G_1 and in G_2. In particular, we show that every series-parallel graph G has a grid drawing on a (2n/3)x(2n/3) grid and such a drawing can be found in linear time.

Note: Refreshments will be served immediately following the lecture in the ECS room # 668 adjacent to room 660.

All are welcome!