# What's the first non-planar graph of the first $n$ numbers where edges show divisibility?

Let $$G_n$$ be a graph with vertices $$v_1, v_2, v_3,\dots, v_n$$, where there is an edge between $$v_i$$ and $$v_j$$ if and only if either $$v_i$$ divides $$v_j$$ or vice versa. Is there a value $$n$$ such that $$G_n$$ is non-planar, ie cannot be drawn in the plane without intersecting edges? If so, what is the least value of $$n$$ for which this happens? By way of example, the drawing below shows that $$G_{12}$$ is planar.

$$G_{14}$$ is planar: From your $$G_{12}$$ sketch, relocate $$7$$ into the $$1{-}2{-}6$$ triangle. This allows you to add $$14$$ with edges to $$1$$, $$2$$, an $$7$$. And the prime $$13$$ can be placed anywhere in the outer region.
One readily sees that the five numbers $$1,2,4,8,16$$ form a $$K_5$$, hence $$G_{16}$$ is not planar.
So what about $$G_{15}$$? It turns out, we would have a $$K_{3,3}$$ with vertices $$1,2,3$$ and $$6,12,m$$ if there were another common multiple of $$2$$ and $$3$$ available. While there is no such $$m$$, we have $$5$$, which is indirectly linked to $$3$$ via $$15$$ and to $$2$$ via $$10$$. Therefore $$G_{15}$$ is not planar.