1981 | OriginalPaper | Buchkapitel
Minimum Edge Length Planar Embeddings of Trees
verfasst von : Walter L. Ruzzo, Lawrence Snyder
Erschienen in: VLSI Systems and Computations
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Valiant [1] showed how to embed any binary tree into the plane in linear area without crossovers. The edges in this embedding have a maximum length of 0($$ \sqrt {n} $$) With Paterson, we [2] showed that a complete binary tree can be embedded in the plane with maximum edge length of 0($$ \sqrt {n} $$/log n) and we argued the importance of short edge length for VLSI design and layout. Here we show that every binary tree can be embedded in the plane with all three properties: linear area, no crossovers, and 0($$ \sqrt {n} $$/log n) maximum edge length. This improves a result of Bhatt and Leiserson [3] — a graph with an n1/2-ε separator theorem can be embedded (perhaps with crossovers) in linear area and with a maximum edge length of 0($$ \sqrt {n} $$) — for the case of binary trees. In the paper we also observe that Valiant’s result can be extended to the case of oriented trees [7].