Circular-arc hypergraphs: Rigidity via connectedness

A circular-arc hypergraph H is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set V(H) such that every hyperedge is an arc of consecutive vertices. We give a criterion for the uniqueness of an arc ordering in terms of connectedness properties of If. This generalizes the relationship between rigidity and connectedness disclosed by Chen and Yesha (1991) in the case of interval hypergraphs. Moreover, we state sufficient conditions for the uniqueness of tight arc orderings where, for any two hyperedges A and B such that A subset of B not equal V(H), the corresponding arcs must share a common endpoint. We notice that these conditions are obeyed for the closed neighborhood hypergraphs of proper circular-arc graphs, implying for them the known rigidity results that were originally obtained using the theory of local tournament graph orientations. (C) 2016 Elsevier B.V. All rights reserved.