Fáry's theorem

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

YouTube Encyclopedic

1/1
Views:
1 247

Transcription

Hi! I'm with the University of New South Wales, in particular the School of Mathematics and Statistics. My name is Thomas Britz and I'm going to be looking at Problem 27 part a of Topic 5 which is about graph theory, in the course MATH1081, Discrete Mathematics. In this problem here, we're looking at a graph and we want to show that it's planar. That means that we can redraw the graph in such a way that all of the edges are not crossing each other; that no edges cross each other. Now, you can see here that we've got lines, or the lines representing the edges, that are crossing each other. We've got a crossing there, there and there, so we have to take this picture of the graph and draw a new picture, a new representation of the graph, in such a way that we don't have any crossings like this. So, before we do that, I've got 2 comments to make. The first is about the type of problem that we have here. We have to show that a graph is planar so then we just redraw and that's fine. You could do it in other ways but that's a simple way to do it. The other type of problem that you often encounter about planarity of graphs is that you have to show the graph is not planar and there you could try to redraw it and say: "Ah! We can't do it", or whatever. But a better way would be to use Kuratowski's Theorem. So, we have two different types of problems here. Or mainly two different of problems. We have to show that a graph is not planar in which case you could use Kuratowski's Theorem or that that a graph is planar in which case you just redraw it in a planar way, so that none of the edges are crossing. The second comment is that this graph is a particular graph. It is sort of nearly diabolical, in the sense that if we added one more line, then we get a pentagram and a pentagram, or in other words, K_5, the complete graph on 5 vertices, that's actually not planar so if you took this new graph here, K_5, and tried to redraw it in a planar way, you'd fail! And you're very welcome to try that just to convince yourself. But if we just take one edge out, like this, then apparently this is a planar graph. And that's what we have to show. So, let's do that! The way that I think of it when redrawing these graphs is that each of the vertices is like a pin or mail in a wooden board and the edges are like rubber bands between the pins. and we take the pin out and move it somewhere else or we stretch a rubber band and so forth. It could be pretty cool to have a wooden board with pins and rubber bands and everything. We've got a whiteboard; that'll have to do. So, let's do that. OK, let's draw some vertices. We've got A, B, C. I'm not moving the vertices much at the moment I'm just being a bit lazy and just drawing the same graph as far as I can, until I run into problems. Draw the outer edges first for instance. That seems to be going well: no crossings there of course. I can draw these two edges for instance; let's see, this one and this one. Now I run into trouble because I can't add any more edges. There are two more: there's from A to E and from C to D. A to E would cross this one here, and C to D would cross this one here. So what do I do? Well, I can stretch my rubber band, so to speak. Take this line from A to E and stretch it, like this. Now it's all bendy but it doesn't intersect anything. It doesn't cross any of the other lines. So that's what we want. What about this one from C to D? We can stretch that one too. So here we've got it here and we stretch it but that's not going to work because it will always intersect this line here, A to E. So it always crosses. So we have to do something else. So we have to maybe bend another edge or move one of the vertices or something. So what can we do? Well, we could for instance take this one here B to E and bend it so make it go all curvy out there, pull the rubber band, and now there's room for us to draw the C to D edge and we've done! We've drawn all of the edges in slightly different ways than before in such a way that they no longer intersect; So this is a planar representation of the graph; so the graph is planar, and there we go. Now, you might be a bit annoyed at these bendy lines. If you really want the lines to be straight, then you could ask: Could we have redrawn it in such a way that the lines are straight? And the answer is: Yes you can! There's a famous theorem, I think by Fáry in the 1920s if I'm not incorrect and please correct me if I am [I was: 1948. The theorem was also proved independently in 1936 by Wagner and in 1951 by Stein.] that you can always take a finite graph like this and draw it in such a way that (it has to be simple but apart from that) redraw it in such a way that all of the lines are in fact straight. So, cool! We should be able to do this here too. So how could we do it? Well, if we wanted this bendy line to be straight, then it would be dissecting this and this line. So, if we instead got rid of those lines or moved them so that they wouldn't intersect, like this, put them up here for instance, then there's suddenly room to straighten out this bendy line. Now we have this edge being represented by this straight line here. Well, it's supposed to be straight; I'm drawing it a little bit messily. Here, we should write D because we've moved D up there. We've taken our pin out of the wooden board and placed it up there. Okay, what about this bendy line? Well, we could do the same sort of thing. We could move this vertex in, by removing the pin from the board and placing down it somewhere else, like for instance here. So this is where we've moved vertex C closer and now we can take this bendy line and straighten it out, like so. And there we go! We have another representation of the graph here that is planar, a planar representation, so none of the edges cross and you see that they are now all straight lines. Well, 'supposed to be, apart from my bad drawing of them. They are all straight lines, and we're done! So that's another solution. Well, thank you very much!

Proof

One way of proving Fáry's theorem is to use mathematical induction.^[1] Let $G$ be a simple plane graph with $n$ vertices; we may add edges if necessary so that $G$ is a maximally plane graph. If $n$ < 3, the result is trivial. If $n$ ≥ 3, then all faces of $G$ must be triangles, as we could add an edge into any face with more sides while preserving planarity, contradicting the assumption of maximal planarity. Choose some three vertices $a, b, c$ forming a triangular face of $G$ . We prove by induction on $n$ that there exists a straight-line combinatorially isomorphic re-embedding of $G$ in which triangle $abc$ is the outer face of the embedding. (Combinatorially isomorphic means that the vertices, edges, and faces in the new drawing can be made to correspond to those in the old drawing, such that all incidences between edges, vertices, and faces—not just between vertices and edges—are preserved.) As a base case, the result is trivial when $n = 3$ and $a$ , $b$ and $c$ are the only vertices in $G$ . Thus, we may assume that $n$ ≥ 4.

By Euler's formula for planar graphs, $G$ has $3 n - 6$ edges; equivalently, if one defines the deficiency of a vertex $v$ in $G$ to be $6 - deg (v)$ , the sum of the deficiencies is $12$ . Since $G$ has at least four vertices and all faces of $G$ are triangles, it follows that every vertex in $G$ has degree at least three. Therefore each vertex in $G$ has deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex $v$ with at most five neighbors that is different from $a$ , $b$ and $c$ . Let $G'$ be formed by removing $v$ from $G$ and retriangulating the face $f$ formed by removing $v$ . By induction, $G'$ has a combinatorially isomorphic straight line re-embedding in which $abc$ is the outer face. Because the re-embedding of $G'$ was combinatorially isomorphic to $G'$ , removing from it the edges which were added to create $G'$ leaves the face $f$ , which is now a polygon $P$ with at most five sides. To complete the drawing to a straight-line combinatorially isomorphic re-embedding of $G$ , $v$ should be placed in the polygon and joined by straight lines to the vertices of the polygon. By the art gallery theorem, there exists a point interior to $P$ at which $v$ can be placed so that the edges from $v$ to the vertices of $P$ do not cross any other edges, completing the proof.

The induction step of this proof is illustrated at right.

Related results

De Fraysseix, Pach and Pollack showed how to find in linear time a straight-line drawing in a grid with dimensions linear in the size of the graph, giving a universal point set with quadratic size. A similar method has been followed by Schnyder to prove enhanced bounds and a characterization of planarity based on the incidence partial order. His work stressed the existence of a particular partition of the edges of a maximal planar graph into three trees known as a Schnyder wood.

Tutte's spring theorem states that every 3-connected planar graph can be drawn on a plane without crossings so that its edges are straight line segments and an outside face is a convex polygon (Tutte 1963). It is so called because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

Steinitz's theorem states that every 3-connected planar graph can be represented as the edges of a convex polyhedron in three-dimensional space. A straight-line embedding of $G,$ of the type described by Tutte's theorem, may be formed by projecting such a polyhedral representation onto the plane.

The Circle packing theorem states that every planar graph may be represented as the intersection graph of a collection of non-crossing circles in the plane. Placing each vertex of the graph at the center of the corresponding circle leads to a straight line representation.

Unsolved problem in mathematics:

Does every planar graph have a straight line representation in which all edge lengths are integers?

(more unsolved problems in mathematics)

Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers.^[2] The truth of Harborth's conjecture remains unknown. Integer-distance straight line embeddings are known to exist for cubic graphs.^[3]

Sachs (1983) raised the question of whether every graph with a linkless embedding in three-dimensional Euclidean space has a linkless embedding in which all edges are represented by straight line segments, analogously to Fáry's theorem for two-dimensional embeddings.

Notes

^ The proof that follows can be found in Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5th ed.), CRC Press, pp. 259–260, ISBN 9781439826270.
^ Harborth et al. (1987); Kemnitz & Harborth (2001); Mohar & Thomassen (2001); Mohar (2003).
^ Geelen, Guo & McKinnon (2008).

References

Fáry, István (1948), "On straight-line representation of planar graphs", Acta Sci. Math. (Szeged), 11: 229–233, MR 0026311.
de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, S2CID 15230919.
de Fraysseix, Hubert; Pach, János; Pollack, Richard (1990), "How to draw a planar graph on a grid", Combinatorica, 10: 41–51, doi:10.1007/BF02122694, MR 1075065, S2CID 6861762.
Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Straight line embeddings of cubic planar graphs with integer edge lengths" (PDF), Journal of Graph Theory, 58 (3): 270–274, doi:10.1002/jgt.20304.
Harborth, H.; Kemnitz, A.; Moller, M.; Sussenbach, A. (1987), "Ganzzahlige planare Darstellungen der platonischen Korper", Elem. Math., 42: 118–122.
Kemnitz, A.; Harborth, H. (2001), "Plane integral drawings of planar graphs", Discrete Mathematics, 236 (1–3): 191–195, doi:10.1016/S0012-365X(00)00442-8.
Mohar, Bojan (2003), Problems from the book Graphs on Surfaces.
Mohar, Bojan; Thomassen, Carsten (2001), Graphs on Surfaces, Johns Hopkins University Press, pp. roblem 2.8.15, ISBN 0-8018-6689-8.
Sachs, Horst (1983), "On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem", in Horowiecki, M.; Kennedy, J. W.; Sysło, M. M. (eds.), Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 230–241, doi:10.1007/BFb0071633, ISBN 978-3-540-12687-4.
Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148, ISBN 9780898712513.
Stein, S. K. (1951), "Convex maps", Proceedings of the American Mathematical Society, 2 (3): 464–466, doi:10.2307/2031777, JSTOR 2031777, MR 0041425.
Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387.
Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung, 46: 26–32.

This page was last edited on 26 May 2024, at 04:54

From Wikipedia, the free encyclopedia