Adapted from the authors' introduction: ''The problem we address in this paper is an embedding problem for a class of graphs which we call rectilinear graphs. These graphs are important in many VLSI layout problems. In fact, this problem arose in the implementation of ALI, a procedural language for VLSI design currently under development at Princeton. An embedding algorithm can be used to automate the production of VLSI layouts in many procedural design systems. The following is an informal description of rectilinear graphs and their embeddings. The vertices of a rectilinear graph have degree at most four. The edges incident on each vertex are given distinct labels from the set \(\{\) Left, Right, Up, Down\(\}\). Suppose we place the vertices on the grid points of a rectangular grid, and for each edge draw a straight line segment between its endpoints. We call the result an embedding of the graph, if the edges lie along grid lines, no two edges cross, and the directions of the edges at each vertex are consistent with their labels. Consider the following model for VLSI layout design. A VLSI layout is described hierarchically using cells and wires that connect the cells together. Each cell C is enclosed within a rectangle R(C), and has four lists of pins, one each for the left, top, right, and bottom of rectangle R(C). Each wire w is denoted by a pair of pins \((p_ i,p_ j)\), such that \(p_ i\) and \(p_ j\) are pins of different rectangles, and are of opposite types. For example, if \(p_ i\) is a right pin then \(p_ j\) should be a left pin. Given such a description of a VLSI layout, our aim is to produce an embedding of the description on the plane, such that (i) no two bounding rectangles touch each other, (ii) the pins appear in the correct order on the bounding rectangles, (iii) the wires are straight and rectilinear, and (iv) no two wires cross each other. Lateron, we can fill each bounding rectangle R(C) with the embedding of the cell C in the same manner. The restriction that wires cannot be bent may seem unrealistic, but this is certainly the case in many design systems including ALI. If a wire has to be bent, the user specifies that by breaking up the wire into several straight wires and placing cells at each of the turn points of the wire. In ALI, for example, the user can incorporate routing algorithms in an ALI program to determine how the wires are to be bent. The restriction that wires cannot cross implies that we are dealing with the wires on a single layer. For a layout with multiple layers, it is clearly necessary that the wires on each layer do not cross. It is easy to observe that the above description of a layout induces a rectilinear graph, whose vertices are the pins and the corners of the bounding rectangles, and whose edges are the wires and the segments created on the bounding rectangles by the vertices. For VLSI applications, we need efficient algorithms to recognize and then actually embed rectilinear graphs. In this paper, we present an O(n) recognition algorithm and an \(O(n^ 2)\) embedding algorithm, where n is the number of vertices in the graph. In addition to the algorithms, general results on rectilinear graphs and their embeddings are included. The paper concludes with a mention of open problems.''