planar hypergraph

Straight line representation of planar linear hypergraphs ★★

Author(s): de Fraysseix; Ossona de Mendez

Conjecture   Every planar linear hypergraph $ \mathcal H $ has a straight line representation in the plane which maps each vertex $ v $ to a point $ p(v) $ and each edge $ E $ to a straight line segment $ s(E) $, in such a way that:
    \item for each vertex $ v $ and each edge $ E $, we have: $$p(v)\in s(E)\quad\iff\quad v\in E$$ \item for each couple of distinct edges $ E_1,E_2 $, we have $$s(E_1)\cap s(E_2)=\{p(v): v\in E_1\cap E_2\}$$

Keywords: intersection graph; planar hypergraph

Syndicate content