de Fraysseix, Hubert

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

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