A Provably Good Linear Algorithm for Embedding Graphs in the Rectilinear Grid
Roberto Tamassia, Ioannis G. Tollis · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1985
planar graph, planar embedding, VLSI layout, W-visibility F IE L D I GROUP I SUB.GR. ■ ------r--------1 --------------representation A BSTRA C T (C o n tin u e on reverse if n ecessa ry a n d id e n tif y by b lock n u m b e r )In this paper we consider planar embeddings of n-node planar graphs in the rectilinear grid, where vertices are grid points and edges are nonintersection grid paths."We present a new embedding algorithm that runs in linear time.The total number of bends in the embeddings constucted by our algorithm is very small.Furthermore, the embeddings occupy 0(n ) area, which is the best possible in the worst case.Our results are important in the design of VLSI chips.Other applications can be found in the areas of communication by light or microwave, transportation in space, and aesthetic layout of diagrams.