Drawing non-intersecting curves (or segments) connecting non-adjacent vertices in a regular polygon

Here is a graph-theoretic proof that you can draw at most $2(n-3)$ diagonals. Let $G$ be a graph whose vertices are the $n$ vertices of the polygon and whose edges are the sides and the curves we draw. Suppose $G$ has $m$ edges (therefore, the number of diagonal curves drawn is $m-n$). Let $f$ denote the number of connected regions inside and outside the polygon (both bounded and unbounded regions).

Note that $G$ is a planar graph. By Euler's Formula, $$n-m+f=2,.$$ Now, each connected region has a boundary formed by at least three edges. Each edge borders exactly two regions. Thus, $$3fleq 2mtext{ or }fleq frac{2}{3},m,.$$ Hence, $$2=n-m+fleq n-m+dfrac{2}{3},m=n-frac13,m,.$$ This means $$mleq 3(n-2)=3n-6,.$$ Hence, $$m-nleq (3n-6)-n=2n-6=2(n-3),.$$ It is easy to see that $2(n-3)$ segments can be drawn. See brainjam's answer for an example.

If you can use curves outside of the polygon then the problem would be the same as joining non-adjacent vertices on a spherical polygon. You can do it on the "outside" and the "inside", and get a maximum of $2(n-3)$ joins and at that point the sphere is divided into topological triangles and no further join is possible.

You still have to use curves, as opposed to straight lines (i.e. geodesics/great circles), because sometimes the geodesic lines will be forced to cross. See Joseph O’Rourke's Computational Geometry Column 51 for an illustration of how geodesics don't work.