Placing $n$ vertices in the plane such that no 3 edges cross the same point Problem
I would like to embed a graph containing $n$ vertices in the plane. Is there a systematic way to assign coordinates such that no matter what edges the graph contains, no three edges will cross at a single point? The edges should be straight lines.
Context
I am working on a problem that requires a transformation of a regular graph (unweighted, undirected) to a planar graph, and my solution involves embedding the given graph in the plane, and then replacing every edge crossing with a new vertex. For this method to work, I need to make sure that no three edges cross at a single point.
I can get around this by forcing extra edges to circle around the point at different distances, like this:
5-way edge crossing
But my solution would be simpler if there was a way to place vertices such that this is never possible and there was a simple explanation why. Then I wouldn't need to go to the trouble of explaining how to avoid $k$-way crossings for $k > 2$, and the reader would have an easier time comprehending the solution.
Ideas
I am looking for a scheme such as: Place vertex $i$ at coordinates $(i, i^2)$ (where $0 \le i \le n - 1$). Using a convex function (such as the square function) is good because it ensures that no edge will ever cross a vertex, however I don't know if this scheme can lead to a 3-way edge crossing.
Another possibility is to arrange the vertices around a circle, but they can't be evenly spaced, otherwise there would be many 3- (or more) way edge crossings.
 A: The simplest explanation is to say: pick $n$ random points around the circle. This works with probability $1$, because there are only finitely many sets of $3$ edges, and the probability that a set of $3$ edges has a single crossing is $0$. (If you fix $5$ of the $6$ vertices, there is only one location around the circle where the $6^{\text{th}}$ vertex can be to create a triple crossing; there is a $0$ probability that a random point on the circle will end up at that location.)
But we can also create some concrete formulas that have this effect.
For example, suppose we use the points $(x,x!)$ for $x=1, \dots, n$. This is not only a convex function, but a very quickly growing one. As such, it has the following property:
Lemma. Take four points $A(a,a!)$, $B(b,b!)$, $C(c,c!)$, $D(d,d!)$ where $a,b,c,d$ are positive integers in ascending order. Then the intersection point of $AC$ and $BD$ has $x$-coordinate between $b$ and $b+1$.
Proof. At the $x$-coordinate of $b+1$, the $y$-coordinate of line $BD$ is $$\frac1{d-b} \cdot d! + (1 - \frac1{d-b}) \cdot b! > \frac1{d-b} \cdot d! > \frac1d \cdot d! = (d-1)! \ge c!$$ so it is already higher than any point of line segment $AC$. $\qquad\square$
(Convexity ensures that when two segments intersect, they can be labeled $AC$ and $BD$ so that $A,B,C,D$ appear in that order on the curve.)
This lemma rules out any triple intersections. Say that an intersection point with $x$-coordinate between $b$ and $b+1$ "belongs" to the point $(b,b!)$. Then which point does a triple intersection belong to? If $AD \cap BE = AD \cap CF$ (and $A,B,C,D,E,F$ appear in that order on the curve), then the same intersection point belongs to both $B$ and $C$, which is impossible.
