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

Drawings


Graph Theory » Topological G.T. » Drawings

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $ P \subseteq {\mathbb R}^2 $ is $ n $-universal if every $ n $ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $ P $, and all edges are (non-intersecting) straight line segments.

Question   Does there exist an $ n $-universal set of size $ O(n) $?

Keywords: geometric graph; planar graph; universal set

Posted by mdevos
updated May 22nd, 2007
add new comment
Graph Theory » Topological G.T. » Drawings

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

Posted by taxipom
updated September 26th, 2007
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content