Simplest graph that is not a segment intersection graph

Question

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an edge $v_iv_j$ for every pair of segments $s_i, s_j$ that intersect.

Let us call a graph $G$ an intersection graph if there exists a collection of straight-line segments $S$ such that $G(S)=G$.

Which is the simplest (or a relatively simple) graph $G$ which is not an intersection graph?

(Background: Not all graphs are intersection graphs, since the number of $n$-vertex intersection graphs is only $2^{O(n\log n)}$ (can't find the reference right now), whereas the total number of $n$-vertex graphs is $2^{\Theta(n^2)}$.)

Answer 1

All you need is a graph consisting of vertices and edges which would represent segments that are impossible in your geometry.

Consider an intersection graph with a set of vertices that contains eight elements $v_1$ through $v_8$. Let the edges be defined such that $v_1$ intersects $v_2$ and $v_8$, $v_2$ intersects $v_1$ and $v_3$, ... etc. Any geometric model of this graph must produce a closed eight sided polygon.

For each edge $e_{xy}$ in the graph, add five new vertices $w_{xyab}$ where $a$ and $b$ are the pairs of segments in the octagon that intersect, and $a \ne b \ne x \ne y$. Each $w_{xyab}$ intersects $v_a$, $v_b$, $v_x$, and $v_y$, but never any $w$.

I believe this is a graph that is impossible to model as intersecting coplanar segments. Proof to follow.

Answer 2

I think I have the solution: Take a nonplanar graph, say $K_5$. Add a vertex in the middle of each edge. We get a graph $G$ with $5$ "blue" vertices of degree $4$ and $5$ "red" vertices of degree $2$. I think $G$ is not realizable as an intersection graph of segments. If it were, we could obtain a planar embedding of $K_5$ by putting a vertex arbitrarily in each blue segment, and join the vertices to one another with piecewise linear arcs that go very close to the blue segments, and through the red segments.