Takao Nishizeki (西関 隆夫, Nishizeki Takao, 1947 – 30 January 2022^[1]) was a Japanese mathematician and computer scientist who specialized in graph algorithms and graph drawing.

Education and career

Nishizeki was born in 1947 in Fukushima, and was a student at Tohoku University, earning a bachelor's degree in 1969, a master's in 1971, and a doctorate in 1974. He continued at Tohoku as a faculty member, and became a full professor there in 1988.^[2] He was the Dean of the Graduate School of Information Sciences, Tohoku University, from April 2008 to March 2010. He retired in 2010, becoming a professor emeritus at Tohoku University, but continued teaching as a professor at Kwansei Gakuin University until March 2015.^[3] He was an Auditor of Japan Advanced Institute of Science and Technology from April 2016 to October 2018.

Contributions

Nishizeki made significant contributions to algorithms for series–parallel graphs,^[4] finding cliques in sparse graphs,^[5] planarity testing^[6] and the secret sharing with any access structure. He is the co-author of two books on planar graphs and graph drawing.^[7]

In 1990, Nishizeki founded the annual International Symposium on Algorithms and Computation (ISAAC).^[8]

Awards and honors

At the 18th ISAAC symposium, in 2007, a workshop was held to celebrate his 60th birthday.^[8]

In 1996, he became a life fellow of the IEEE "for contributions to graph algorithms with applications to physical design of electronic systems."^[9] In 1996 he was selected as a fellow of the Association for Computing Machinery "for contributions to the design and analysis of efficient algorithms for planar graphs, network flows and VLSI routing".^[10] Nishizeki was also a foreign fellow of the Bangladesh Academy of Sciences;^[11] one of his students and frequent co-authors, Md. Saidur Rahman, is from Bangladesh.

Selected publications

Books

• Nishizeki, T.; Chiba, N. (1988), Planar Graphs: Theory and Algorithms, North-Holland Mathematics Studies, vol. 140, North-Holland, ISBN 978-0-444-70212-8, MR 0941967.
• Nishizeki, Takao; Rahman, Md. Saidur (2004), Planar Graph Drawing, Lecture Notes Series on Computing, vol. 12, World Scientific, doi:10.1142/5648, ISBN 978-981-256-033-9, MR 2112244.

Research articles

• Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328, MR 0666771, S2CID 16082154.
• Chiba, Norishige; Nishizeki, Takao (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, MR 0774940, S2CID 207051803.
• Chiba, Norishige; Nishizeki, Takao; Abe, Shigenobu; Ozawa, Takao (1985), "A linear algorithm for embedding planar graphs using PQ-trees", Journal of Computer and System Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2, MR 0788831.
• Ito, Mitsuru; Saito, Akira; Nishizeki, Takao (1989), "Secret sharing scheme realizing general access structure", Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72 (9): 56–64, doi:10.1002/ecjc.4430720906.