Flexibility of Steiner trees in uniform orientation metrics

Marcus Brazil, Pawel Winter, Martin Zachariasen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


We present some fundamental flexibility properties for minimum length networks (known as Steiner minimum trees) interconnecting a given set of points in an environment in which edge segments are restricted to λ uniformly oriented directions. These networks are referred to as λ-SMTs. They promise to play an increasingly important role in the future of optimal wire routing in VLSI physical design, particularly for the next generation of VLSI circuits. In this paper we develop the concept of a flexibility polygon for a λ-SMT, which is a region representing the union of all (minimum length) λ-SMTs with the same topology on a given set of points. We show that this polygon can be constructed, for a given point set and given topology, in linear time. We discuss some of the future applications of this polygon, which can be thought of as a geometric representation of the amount of flexibility inherent in a given λ-SMT.

Original languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publicationISAAC 2004
EditorsR. Fleischer, G. Trippen
Place of PublicationGermany
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-30551-4
ISBN (Print)978-3-540-24131-7
Publication statusPublished - 2004
EventAlgorithms and Computation: 15th International Symposium, ISAAC 2004 - Hong Kong, China
Duration: 20 Dec 200422 Dec 2004
Conference number: 15

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceAlgorithms and Computation
CityHong Kong


Dive into the research topics of 'Flexibility of Steiner trees in uniform orientation metrics'. Together they form a unique fingerprint.

Cite this