Basser Seminar Series

Inner Rectangular Drawings of Plane Graphs: Application of Graph Drawing to VLSI Layouts

Professor Takao Nishizeki
Tohoku University, Japan

Thursday 15 February 2007, 3-4 pm (NOTE Different day and time)

School of IT Building, Lecture Theatre 123, Level 1

Abstract

A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle. An inner rectangular drawing has some applications to VLSI layouts.

In this talk we show that a plane graph $G$ has an inner rectangular drawing $D$ if and only if a new bipartite graph constructed from $G$ has a perfect matching.

We also show that $D$ can be found in time $O(n^{1.5}/\log n)$ if $G$ has $n$ vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed.

This is a joint work with K. Miura and H. Haga.

Speaker's biography

Takao Nishizeki is currently Professor of algorithm theory in the Graduate School of Information Sciences at Tohoku University in Japan.

He received the B.E., M.E. and D.E. degrees in electrical communication engineering from Tohoku University in 1969, 1971 and 1974, respectively. Upon graduation, he joined the faculty at Tohoku University, where in 1976 he was appointed as Associate Professor of the Department of Electrical Communications, then in 1988 was promoted to Professor. From 1977 to 1978 he was a Visiting Research Mathematician at Carnegie-Mellong University.

His research interests are in the field of algorithms for planar graphs, edge-coloring, network flows, VLSI routing and cryptology. He has co-authored two books, edited five books, and published more than 100 technical papers in scientific journals. Nishizeki also founded the International Symposium on Algorithms and Computation (ISAAC) which has been held in Asian-Pacific region annually since 1990. He has been consistently on program committees of international conferences and regularly on editorial boards of several journals including Algorithmica, Journal of Graph Algorithms and Applications,' and Journal of Combinatorial Optimization. He is a Fellow member of IEEE and ACM.