On the rectilinear Steiner problem

Andreas Blass, Yuri Gurevich

Bulletin of the European Association for Theoretical Computer Science · 2017 · 22 citations · 0 references

Concepts

Abstract

This is a gentle introduction to the Rectilinear Steiner Problem. The interest in the Rectilinear Steiner Problem is related to the Very Large-Scale Integration (VLSI) technology that combines thousands of transistors into a single chip. Our note is based on the pioneering paper of Maurice Hanan. The main result of Hanan is an algorithm reducing any solution to a solution within a so-called Hanan grid. We simplify Hanan’s algorithm.