Always a planar-drawn cycle through $n$ points Given $n$ points in the plane, can we always find a cycle through all of them that has only straight line edges and no edges intersect (planar-drawn)?

Intuitively the answer is yes, but I am struggling with a proof. In the example above, the $2^{nd}$ graph demonstrates an incorrect algorithm, whereas the last graph demonstrates a working algorithm. I have tried using induction.
For different variants there are constraints - this is not always possible if the points are colored (e.g. if two points of one color lies on non-adjacent points of the convex hull and any path between them partitions the other color).
 A:  

The answer is yes.
First we draw a cycle with the outmost vertices such that other vertices are within the cycle. (This is step 2 in above picture.)
Then we repeat this for vertices that are not on the first cycle and draw the second cycle.
We repeat this until all vertices lie on a unique simple closed cycle.
Now we delete an edge from each two adjacent cycles and connecting vertices such that two cycles exchange in one longer cycle. Then repeat this until we have had a cycle consists all vertices.
A: Yes. Let $A$ be a vertex of a convex hull. Draw rays $AP_1,\dots,AP_{n-1}$ to other points, let them go in this order counted counterclockwise. Then $AP_1P_2\dots P_{n-1}A$ is what you need.
A: Every shortest cycle through the $n$ points is noncrossing. This can be easily shown by contradiction: if two edges are crossing, they form the diagonals of a convex $4$-gon, and we can replace them by a pair of opposite sides of the $4$-gon (one choice gives a cycle, the other choice gives two cycles). By the triangle inequality, the new cycle is shorter than the original one.
A: Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:

 



1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.
25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.

Subsequently, Michael Gemignani removed the general-position assumption,
relaxed to not-all-collinear. And then Grünbaum offered a simple proof that leads to
an $O(n \log n)$ algorithm.1
Fedor Petrov's solution is known as a star polygonization.
Finding a minimal-area simple polygonization is NP-hard.
