Consider an $n$-gon where we denote the points by $v_1, \dots, v_n$. If we allow each chord (internal edge of the $n$-gon) to have at most $k$ crossings, how many chords can we put into the $n$-gon (denoted as $c(n,k)$). The answer to this question is the density of outer-$k$-planar graphs (+ n for the boundary edges of the $n$-gon): For $k = 0$, we have at most $n-3$ chords. For $k = 1$, we have $1.5n - 4$. One can show that $2n-5$ and $2.25n-6$ holds for $k = 2$ and $3$. Can we generalize this to any $k$?:
Chaplick et al.1 showed that outer-$k$-planar graphs are $d$-degenerate with $d = \lfloor \sqrt{4k+1}+1 \rfloor$, hence we have less than $dn \approx 2\sqrt{k}n$ chords.
Now the best lower bound I can think of (and I suspect to be best possible) only has approximately $\sqrt{k}n$ chords (hence, the upper bound would be off by a factor of $2$).
Alternative views of the problem:
- Consider the adjacency matrix $A$ of an outer-$k$-planar graph. $A$ is symmetric, binary, has only zeroes in the diagonal and ones in the off-diagonal. Now if there exists an edge $(v_i,v_j)$, we have at most $k$ edges that are incident to $v_p$ with $ i < p < j$ and $v_q$ with $q < i$ or $j < q$, hence we have at most $k$ 1-entries in the marked areas, see Figure below.
$okp$ graphs" />- We can consider the intersection graph $IG$ of the graph, i.e. every possible chord is a node of $IG$ and it is connected to another node in $IG$ iff the respective chords in $G$ intersect. Then, the problem is to find a maximum induced subgraph in $IG$ such that the degree is bounded by $k$. This problem is in general known to be NP-hard, but maybe this can be solved for our particular graph. (Note that this somehow has to be extended to any $n$).
One can solve this problem for small $n$ and $k$ with an integer linear programm which yields
\begin{array}{c|rrrrrrrrrrrrr} {_n\,\backslash\, ^k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 4 & 1 & 2 & & & & & & & & & & & \\ 5 & 2 & 3 & 5 & & & & & & & & & & \\ 6 & 3 & 5 & 6 & 8 & 9 & & & & & & & & \\ 7 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & & & & & & \\ 8 & 5 & 8 & 11 & 11 & 13 & 14 & 16 & 18 & 19 & 20 & & & \\ 9 & 6 & 9 & 12 & 14 & 15 & 17 & 18 & 20 & 22 & 23 & 24 & 25 & 27 \end{array} Interesting observation : $c(8,2) = c(8,3)$
You are asking about a maximal possible number of edges in an outer $k$-planar graph (minus $n$ for the number of sides of the $n$-gon). As far as I know, these graphs are a very recent topic in graph theory and they are studied in Würzburg. It is already known that an outer $1$-planar graph with $n$ vertices has at most $2.5n-4$ edges and this bound is tight [A] (that coincides with the second column of your table). But I found no results for bigger $k$, so I have sent a link to your question to Würzburg team.
References
[A] C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.