p-Box: A new graph model
Mauricio Soto, Christopher Thraves Caro
Abstract
In this document, we study the scope of the following graph model:
each vertex is assigned to a box in ℝd
and to a representative element that belongs to that box. Two vertices
are connected by an edge if and only if its respective boxes contain
the opposite representative element. We focus our study on the case
where boxes (and therefore representative elements) associated to
vertices are spread in ℝ. We give both, a
combinatorial and an intersection characterization of the model.
Based on these characterizations, we determine graph families that
contain the model (e. g., boxicity 2 graphs) and others
that the new model contains (e. g., rooted directed path). We also
study the particular case where each representative element is the
center of its respective box. In this particular case, we provide
constructive representations for interval, block and outerplanar
graphs. Finally, we show that the general and the particular model are
not equivalent by constructing a graph family that separates the two
cases.
Full Text: PDF PostScript