Home » Subject » Graph Theory » Topological G.T. » Drawings

Straight line representation of planar linear hypergraphs (Solved)

Importance: Medium ✭✭
Author(s): de Fraysseix, Hubert
Ossona de Mendez, Patrice
Subject: Graph Theory
» Topological Graph Theory
» » Drawings
Keywords: intersection graph
planar hypergraph
Recomm. for undergrads: no
Posted by: taxipom
on: September 4th, 2007
Solved by: Daniel Gonçalves (conterexample submitted as a note to the European Journal of Combinatorics
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\}$$

Bibliography

*[dFOdM] Hubert de Fraysseix, Patrice Ossona de Mendez: Stretching of Jordan arc contact systems, Discrete Applied Mathematics 155 (2007), no. 9, 1079--1095.


* indicates original appearance(s) of problem.
add new comment