Containment Graphs, Posets, and Related Classes of Graphs
share
In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let Z be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a Z-containment graph provided one can assign to each vertex v_i ∈ V a set S_i ∈ Z such that v_i v_j ∈ E if and only if S_i ⊂ S_j or S_j ⊂ S_i . Similarly, we call a (strict) partially ordered set P = (V, <) a Z-containment poset if to each v_i ∈ V we can assign a set S_i ∈ Z such that v_i < v_j if and only if S_i ⊂ S_j. Obviously, G is the comparability graph of P. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in d-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to “injective” containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for “strong” containment classes of graphs.
READ FULL TEXT