How many ways can one draw a graph? (Q879163)

Let \(G\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). A string representation of \(G\) is an assignment of simple continuous arcs to the elements of \(V(G)\) such that two arcs cross each other if and only if the corresponding vertices of \(G\) are adjacent. Graph \(G\) is a string graph if it has string representation. We assume that any two arcs share only finitely many points and that at each common point the arcs properly cross, i.e., one arc passes from one side of the other arc to the other side. An intersection point of two arcs is called a crossing. For any \(d>0\) graph \(G\) is a string graph of rank \(d\) if it has a string representation with the property that any two strings have at most \(d\) crossings. A drawing of a graph is a mapping \(f\) which assigns to each vertex of \(G\) a distinct point in the plane and to each edge \(uv\) a continuous arc between \(f(u)\) and \(f(v)\), not passing through the image of any other vertex. In the present paper the authors determine the asymptotic number of string graphs with \(n\) vertices showing that it varies between \(2^{\frac{3}{4}{n\choose 2}}\) and \(2^{(\frac{3}{4}+o(1)){n\choose 2}}\). They also show that the number of all string graphs of rank \(d\) does not exceed \(2^{o(n^2)}\) and apply these results to estimate the number of different drawings of the complete graph \(K_n\) with \(n\) vertices under various side conditions.