The complexity of recognizing $ABAB$-free hypergraphs

The study of geometric hypergraphs gave rise to the notion of $ABAB$-free hypergraphs. A hypergraph H is called $ABAB$-free if there is an ordering of its vertices such that there are no hyperedges $A,B$ and vertices v₁,v₂,v₃,v₄ in this order satisfying v₁,v₃∈ A B and v₂,v₄∈ B A. In this paper, we prove that it is NP-complete to decide if a hypergraph is $ABAB$-free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such as $ABABA$-free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete.