This paper examines the class ofbipartite permutation graphs. Two chaiacterizations of graphs i n this class are presented. These characterizations l ead to a linear time recognition algorithm, and to polynomial time algorithms for a number of NP-complete problems when restricted to graphs i n this class.
Bipartite graphs and permutation graphs are two well known subfamilies of the perfect graphs. Neither of these families is contained in the other, and their intersection is nonempty. This paper shows that graphs which are both bipartite and permutation graphs have good algorithmic properties. These graphs can be recognized in linear time, and several problems which are NP-complete or of unknown complexity for graphs in either of the two larger classes can be solved in polynomial time when restricted to bipartite permutation graphs. These problems include the Hamilton Circuit problem, a variant of the Crossing Number problem, and the minimum fill-in problem.
Definitions
For the most part, this paper uses standard graph theory terminology. Some of the notation and definitions will be explicitly stated in this section.
For a graph G = (V, E), we will often denote 1 VI by n and IE( by m. A linear lime algorithm is an algorithm which takes O(n + m) time.
The set of vertices adjacent to a vertex u is called the neighborhood of u, and is written as N(u). This does not include the vertex LJ itself.
A graph is bipartite, or two-colorable, if its vertices can be partitioned into two independent sets. We will call the two independent sets S and T. If there is more