Characterization and representation problems for intersection betweennesses
For a set system M=(Mv)v?V M = ( M v ) v ? V indexed by the elements of a finite set V V , the intersection betweenness B(M) B ( M ) induced by M M consists of all triples (u,v,w)?V3 ( u , v , w ) ? V 3 with Mu?Mw?Mv M u ? M w ? M v . Similarly, the strict intersection betweenness Bs(M) B s ( M ) induced by M M consists of all triples (u,v,w)?B(M) ( u , v , w ) ? B ( M ) such that u u , v v , and w w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 536]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Buriganas notion of a partial tree representation can be solved efficiently using well-known algorithms.
betweenness trees shortest paths