Is every graph an edge-crossing graph?

Question

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph whose nodes correspond to the edges of $G$ and in which two nodes are adjacent if and only if the corresponding edges cross.

Example. The graph $G$ has four vertices (1–4) and three edges (a–c) where $a = 12$, $b = 13$, $c = 24$. In the circular drawing, $b$ and $c$ cross, so the crossing graph has three nodes and a single edge $bc$.

Here are my questions:

1. Is every simple graph the crossing graph of some circular graph drawing?

2. If not, how does a counterexample look like?

3. If yes, how can such a graph drawing be constructed?

Answer 1

Such graphs are called "circle graphs" and if you search on that phrase you will find some literature. For example, some is around page 56 in this book.

Figure 2 in this paper shows a 7-vertex graph that is not a circle graph, but according to OEIS:A156809 there are two with 6 vertices.

Answer 2

The answer to 1 is no. To see this, note that every edge-crossing graph is a string graph. A string graph is a graph which is the intersection graph of arbitrary curves in the plane. However, there are graphs which are not even string graphs.

One example of a graph which is not a string graph is $K_5$ with each edge subdivided once. To see this, let $G$ be $K_5$ with each edge subdivided once and suppose that $\mathcal{S}$ is a string representation of $G$. Let $S_1, \dots, S_5$ be the strings in $\mathcal{S}$ that correspond to the degree-4 vertices of $G$. Since the degree-4 vertices are an independent set in $G$, these strings are pairwise disjoint. Since the degree-2 vertices are also an independent set in $G$, by shrinking each of $S_1, \dots, S_5$ down to a point in $\mathcal{S}$, we get a planar drawing of $K_5$, which is a contradiction.

Answer 3

No, and you can see this from just a counting argument.

For determining which of the $ n $ chords of the circle intersect, it is enough to know the order of the $ 2n $ endpoints on the circle. (You can assume that no two endpoints coincide.) There are at most $ (2n)!/2^n $ such orders (the two endpoints of a chord aren't distinguishable). On the other hand, there are exactly $ 2^{n(n-1)/2} $ simple graphs on $ n $ nodes. The latter grows faster.

You can even get an explicit bound from this: there are more simple graphs on 16 nodes than arrangement of 13 chords in the circle, so at least one of those graphs can't be generated this way.