Talk:Fáry's theorem

Proof[edit]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Simpler argument[edit]

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)[reply]

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)[reply]