In a multiple interval intersection representation of a graph it is required that at least one interval from each of a pair of adjacent vertices intersect. It is permitted for there to be several such intersections even though these additional intersections are superfluous or redundant. By disallowing such redundancies one arrives at the concept of an irredundant multiple interval representation. This document shows that these irredundant representations can be much more inefficient than representations which allow redundancies. Finally, it is shown that even when some redundancy is permitted, the inefficiency remains. (Author)
展开▼
