Premium
Containment Graphs, Posets, and Related Classes of Graphs
Author(s) -
GOLUMBIC MARTIN CHARLES,
SCHEINERMAN EDWARD R.
Publication year - 1989
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1989.tb22452.x
Subject(s) - annals , containment (computer programming) , center (category theory) , citation , library science , computer science , mathematics , classics , history , chemistry , programming language , crystallography
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 \in V $ a set $S_i \in Z$ such that $v_i v_j \in E$ if and only if $S_i \subset S_j$ or $S_j \subset S_i$ . Similarly, we call a (strict) partially ordered set $P = (V, <)$ a $Z$-containment poset if to each $v_i \in V $ we can assign a set $S_i \in Z$ such that $v_i < v_j$ if and only if $S_i \subset 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.