Layouts with wires of balanced length

Lecture notes in computer sciencePublished 19 November 2005

Bernd Becker, Hans Georg Osthof

DOI10.1007/bfb0023991

Source URL

Citations2

SJR quartileQ2

SJR score0.35

SNIP0.55

Abstract

For any graph (with fixed boundary) there exists a layout, which minimizes the maximum distance of any node to its neighbours. This layout balances the length of the wires (corresponding to graph edges) and is called (length-) balanced layout.Furthermore the existence of a unique 'optimal' balanced layout L with the following properties is proved:i) L is the minimal element of an order defined on the set of layouts of a graph with fixed boundary. ii) L may be constructed as the limit of the 1p-optimal layouts Lp of G. iii) If G is a planar graph with fixed boundary, then the optimal balanced layout L of G is 'quasi-planar'.

Keywords

Engineering

Journal of the ACMP-Complete Approximation Problems

1,715 Citations1976Sartaj Sahni, Teofilo F. Gonzalez

For P- complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete.

View PDF

Closest-point problems

1,062 Citations1975Michael Ian Shamos, Dan Hoey

The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.

Applied Mathematics and ComputationAlgebraic multigrid (AMG): experiences and comparisons

480 Citations1983Klaus Stüben

A special AMG algorithm will be presented, which yields an iterative method which exhibits a convergence behavior typical for multigrid methods.

Bounds on minimax edge length for complete binary trees

76 Citations1981Mike Paterson, Walter L. Ruzzo +1 more

The length of edges in planar graphs is studied to prove matching (to within a constant factor) upper and lower bounds on minimax edge length for four planar embedding problems for complete binary trees.

View PDF

SIAM Journal on ComputingOn the Optimal Layout of Planar Graphs with Fixed Boundary

27 Citations1987Bernd Becker, G. Hotz

For a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, the existence and uniqueness of the optimal layout are shown.

An area-maximum edge length tradeoff for VLSI layout

9 Citations1984Norbert Blüm

It is proved that any layout for G with area Nf(N) has an edge of length Ω(N1/2/f (N) •log N) so that G has no layout which is optimal with respect to both measures.

Information and ControlAn area-maximum edge length trade-off for VSLI layout

4 Citations1985Norbert Blüm

It is proved that any layout for G with area Nf(N) has an edge of length Ω(N1/2/f( N)·log N) and G has no layout which is optimal with respect to both measures.