A certain embedding of a planar graph in the plane

Analyses the graph embedding problem. The major difficulty in dealing with the problem is that the embedding of a biconnected graph is not unique (the order of vertices in the ordered adjacency list is not unique and the vertex sets constituting face boundaries are not unique) and there can be many ways to embed graphs especially those arising in IC layout. The embedding is a graph model of a layout where some elements and connecting lines should be placed apart on the plane. The author presents an algorithm for obtaining an embedding which satisfies the condition that no two vertices in the given vertex subset U appear on the same face boundary. This algorithm is based on the vertex addition algorithm for planarity testing and uses a data structure called a PQ-tree. >