Minimal Steiner Trees for 2k×2kSquare Lattices

✍ Scribed by M. Brazil; T. Cole; J.H. Rubinstein; D.A. Thomas; J.F. Weng; N.C. Wormald

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 417 KB
• Volume: 73
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1996.0004

✦ Synopsis

We prove a conjecture of Chung, Graham, and Gardner (Math. Mag. 62 (1989), 83 96), giving the form of the minimal Steiner trees for the set of points comprising the vertices of a 2 k _2 k square lattice. Each full component of these minimal trees is the minimal Steiner tree for the four vertices of a square.

1996 Academic Press, Inc.

1. Introduction

Consider a finite set of points in the Euclidean plane. The Steiner problem asks us to find a minimal network connecting these points, that is, Article No. 0004 91 0097-3165Â96 12.00