Efficient algorithms for planar embedding of graphs with constraints in placing specified vertices on face boundaries

As a basis of dealing with various constraints arising in IC layout problems we present efficient algorithms for planar embedding of graphs with constraints on vertices in placing them on face boundaries (=meshes, or windows). The constraints considered are: (1) the specified vertices must be placed on a single face boundary, and (2) the specified vertices must be placed on distinct face boundaries. Our algorithms are based on the vertex addition algorithm and implemented using PQ-trees to achieve linear time and space complexities. Basically, the vertex addition algorithm tests all possible planar embeddings, and thus our algorithms can be modified or extended to deal with wide varieties of constraints.