You are here

Steiner Trees on a Checkerboard

by Fan K. Chung, Martin Gardner, and Ronald L. Graham

Award: Carl B. Allendoerfer

Year of Award: 1990

Publication Information: Mathematics Magazine, Vol.62 (1989), pp. 83-96

Summary: How can the points of a regular lattice in the plane be joined by a network of straight lines of shortest possible length.

Read the Article

About the Authors: (from Mathematics Magazine, Vol. 62 (1989)) Fan Chung received her Ph.D. in mathematics from the University of Pennsylvania in 1974. Since then, she has done research in graph theory and combinatorics at Bell Laboratories and Bellcore. She was the Division Manager of the Mathematics, Information Sciences and Operations Research Divsion at Bellcore. She is a professor at the University of California at San Diego. She served on the council of the AMS and on the editorial boards of several journals, and was the editor in chief of the Journal of Graph Theory. Among her research in external and algorithmic problems, one of her favorites is the Steiner tree problem. She has worked on the problem from time to time with both of her coauthors, one of whom is her husband.

Martin Gardner wrote the Mathematical Games column in Scientific American for 25 years. Thirteen book collections of these columns have been published. He is the author of many other books on recreational mathematics, science, philosophy, and literature. His interests in Steiner trees was sparked by setting himself the task -- apparently not attempted before -- of finding a minimal network joining the 81 points of a chessboard.

Ron Graham has spent the past 25 years mainly at AT&T Bell Laboratories with occasional semester visits to Caltech, Princeton, Stanford, and UCLA. During this time he has been involved in a variety of mathematical activities which include teaching, research, juggling, editing, curriculum development, administration, and promoting the public understanding of mathematics. He has worked on various aspects of the subject of this article off and on over the past two decades with his coauthors, one of whom is his wife.

Subject classification(s): Geometry and Topology | Analytic Geometry
Publication Date: 
Friday, February 2, 2007