On factorable extensions and subgraphs of prime graphs.

We investigate cartesian-factorable extensions and subgraphs of prime graphs. We show that minimal factorable extensions and maximal factorable subgraphs are not unique and that finding them is NP-hard. We derive tight bounds on the density of a prime graph's minimal factorable extension. A dynamic programming algorithm is given for finding factorable extensions of certain types of trees.