Talk:Fáry's theorem

Proof

The author of the proof - is a must. I didn't read closely, but it is not the original Fary's proof. `'Miikka 02:40, 30 June 2007 (UTC)

The problem may not be one of missing attribution. I've had some trouble tracking down a publication containing this particular proof, and am a little worried that it may be original research. If so, I guess we should use some other already-published proof. Here's the diff from when I added the proof, by the way. —David Eppstein (talk) 19:26, 16 December 2007 (UTC)

I see a problem with this proof: there may be edges inside the polygon, as some of the edges that were added to triangulate the polygon may be outside. 109.67.149.210 (talk) 21:17, 9 April 2012 (UTC)

The outer face is a triangle; which edges do you think these added edges would be that are outside it and connect vertices not already connected by outer face edges? —David Eppstein (talk) 22:08, 9 April 2012 (UTC)

I'll try to explain what I ment better: the polygon P in G' may not be a face. this is only possible if at least one of the the added edges is outside P. if P is not a face, the proof fails.

however, there is a way to fix the proof, that will even give a stronger result:

if the induction hypothesis is that that for an embedding a graph of n vertices, there exists a homotopic straight-line embedding, the proof works. 109.67.149.210 (talk) 22:57, 9 April 2012 (UTC)

At each step the graph being embedded is maximal planar, so there is only one possible embedding, and no way to get an embedding that isn't homotopic. —David Eppstein (talk) 23:15, 9 April 2012 (UTC)

after some thought I can see that this is true, but its not at all obvious.109.67.149.210 (talk) 23:30, 9 April 2012 (UTC)

Hey, I independently arrived at the same complaint as 109.67.149.210: How do you know that, in the embedding you get by induction, the pentagon is a face, i.e. it does not have stuff inside? I think you can solve this problem by proving, and assuming by induction, a stronger statement: that any given embedding can be straightened out. Gabn1 (talk) 08:41, 30 December 2012 (UTC)

Yes, this seems like an improvement. It doesn't solve the problm of the proof being original research, though. —David Eppstein (talk) 17:59, 30 December 2012 (UTC)

Simpler argument

A simpler argument is the following: if the graph has $n$ vertices, draw it in $R^{n}$ using the points of the usual basis $e_1,\\dots,e_n$ and stright segments where needed. Now show that you can project orthogonally down to a subspace of dimension $n-1$ preserving the property that the edges are disjpoint. For this,it is enough to see that there is a direction in $R^n$ such that no line with that direction intersects two of the segments are interior points (and you can get such a direction using Baire's theorem saying that $R^n$ is of the first category as a topological space). Now you have a rectilinear embedding in $R^{n-1}$. As long as you are not on a plane, you can keep doing this. — Preceding unsigned comment added by 157.92.22.152 (talk) 21:16, 13 June 2016 (UTC)

Where are you using the assumption that the graph is planar? It is certainly the case that you can make mistakes in projecting one dimension at a time; for instance, what do you do if your initial graph is a cycle but by the time you get to three dimensions it is a knotted cycle? How do you then project that to two dimensions? —David Eppstein (talk) 21:22, 13 June 2016 (UTC)