Distinguished Achievement and Contributions Award


Takao NISHIZEKI  Dr. Takao Nishizeki graduated from the Department of Electrical Communications, Faculty of Engineering, Tohoku University in March 1969. He completed his doctorate course in electrical and communications engineering at the same university and was awarded a Ph.D. in March 1974. He became a research associate at the Faculty of Engineering of Tohoku University in April of the same year, and was promoted to an associate professor in June 1976 and a professor in April 1988. From April 1977 through March 1978, he was a visiting mathematician at Carnegie-Mellon University. He retired from the Graduated School of Information Sciences in March 2010, becoming a professor emeritus of Tohoku University, but continued teaching as a professor at the Informatics Department of Kwansei Gakuin University until March 2015. From April 2016 he has been an Auditor of the Japan Advanced Institute of Science and Technology.
   Dr. Nishizeki has undertaken a wide range of research related to computer science, algorithm theory, graph theory and information security, and he has also devoted himself to educating a large number of students who have gone on to become excellent researchers and engineers in academia and industry.
   His major achievements are summarized below.
(1) Linear-time algorithms for structured graphs: graphs representing connection of internets, traffic networks, etc. have distinctive features; most of them are of so-called tree-structures. He showed that most combinatorial problems can be solved in linear time for such graphs. This result inspired the development of the new area of research glinear-time algorithms for structured graphs.h (2) Efficient discrete algorithms: Another research contribution was to design a large number of efficient graph algorithms, based on his own developments in graph theory. A graph is called planar if it can be embedded on the 2-dimentional plane without edge-crossings.
   He gave very efficient algorithms for most of the important combinatorial problems on planar graphs such as plane embedding, colorings, Hamiltonian cycles, independent vertex sets, multi-commodity flows, etc.
(3) Graph drawing algorithms: The problem of drawing graphs suitably under various conditions often appears in numerous areas of science and technology such as visualization of the internet and traffic networks. He is the first who started the algorithmic research of graph drawings. One of his early results in this area was a linear-time algorithm to obtain a convex drawing of planar graphs, in which every inner face is drawn as a convex polygon. He also introduced many new drawing methods such as box-rectangular drawings, inner rectangular drawings, octagonal drawings with prescribed face areas, etc.
(4) Multiple assignment secret sharing schemes: Secret sharing schemes refer to methods for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together. The most famous of these is the Shamirfs (k,n)-threshold scheme, by which any group of k or more players among n participants can together reconstruct the secret but no group of fewer than k players can. Dr. Nishizeki et al. proposed a new scheme called a multiple assignment scheme, which can realize any monotone access structure.
   For the achievements mentioned above, Dr. Nishizeki has received numerous awards such as the IEICE Achievement Award, IEICE Best Paper Award, Funai Information Science Promotion Award, and the MEXT Commendation for Science and Technology, etc. He is a Fellow of many distinguished academic and scientific societies including ACM, IEEE, IEICE, IPSJ and the Bangladesh Science Academy.
   His contributions to society include his service as a vice president of the Information and Systems Society, the director of the Tohoku Section and the Chair of the Technical Committee on Computation of the IEICE, and a member of various committees related to national science and technology policies, for MEXT and the Science Council of Japan. He also founded the International Symposium on Algorithms and Computation, which has grown to be one of the major theory symposiums on computer science.
   As described above, his contributions to the fields of electronics, information and communications have been truly outstanding and we confidently believe that Dr. Nishizeki is worthy of receiving the Distinguished Achievement and Contributions Award from the IEICE.