planar hypergraph

Straight line representation of planar linear hypergraphs ★★

Author(s): de Fraysseix; Ossona de Mendez

\begin{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: \begin{itemize} \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\}$$ \end{itemize} \end{conjecture}

Keywords: intersection graph; planar hypergraph

Syndicate content