10
$\begingroup$

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$.

Example of a graph drawing and its crossing graph

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.