We introduce a new data structure, which we call generalized $PQ$-trees because they behave like Booth and Lueker's $PQ$-trees. Given a ground set of $n$ elements $S$, and $A = {A_{1},\ldots,A_{k}}$ a collection of subsets of $S$, generalized $PQ$-trees allow us to efficiently represent which subsets of $S$ never partially overlap with sets in $A$. We give an $O(kn)$ time sequential algorithm and an $O(kn)$ processor parallel algorithm for computing the generalized $PQ$-tree. Our new data structure can be used to speed up other researchers algorithms for recognizing interval and parity graphs.