# Graphs formed by adding vertices to the circular layout of the complete graph $K_{n}$.

Beginning with the complete graph $K_{n}$ for $n\geq 3$ and construct a new graph $G_{n}$ from it such that $G_{n}$ contains every vertex from the circular graph layout of $K_{n}$.

For instance, if I have $K_{37}$:

And wherever there's a crossing, emplace another vertex, yielding $G_{37}$

• What properties of $G_{n}$ immediately follow from those of $K_{n}$? It's pretty clear that there's a graph homomorphism $\psi_{n}:K_{n}\rightarrow G_{n}$, and also clear that there are some properties of $K_{n}$ which are lost in $G_{n}$.

• Which computational graph theory package would be best for coping with $G_{n}$? Given how fast the vertex count of $G_{n}$ increases, I think I'd need something comfortable with graphs of several thousand vertices

-
No. I mean that every where there is a crossing in the circular layout of $K_{n}$, we emplace a new vertex, yielding $G_{n}$. In the above picture $K_{37}$'s vertices are the points on the periphery, where $G_{37}$'s vertices are the points on the periphery and the crossings. –  deoxygerbe Jun 25 '13 at 20:03