# Talk:Steinitz's theorem

Who was Steinitz who made that theorem? Maybe you should add that? — Preceding unsigned comment added by 193.2.132.123 (talk • contribs) 

You stopped reading before the fourth sentence? —David Eppstein (talk) 17:51, 7 April 2013 (UTC)

This review is transcluded from Talk:Steinitz's theorem/GA1. The edit link for this section can be used to add comments to the review.
Reviewer: Kusma (talk · contribs) 14:01, 8 August 2021 (UTC)
I'll take this one, will make in-depth comments over the next few days. —Kusma (talk) 14:01, 8 August 2021 (UTC)


### Comments
Global comments:

I'm a mathematician (but with very little knowledge of graph theory and discrete mathematics), so I might overlook some pieces of jargon that others would complain about. I will complain about any jargon that I find hard to understand, though.
What I'm missing a bit is the context and importance of the theorem. The lead says that Branko Grünbaum claims it is the most important and deepest result on 3-polytopes. This statement isn't repeated in the article body, and isn't explained. Is it important because it has applications (what are these?) or is it important because it is deep? Is it important as a result about polyhedra or as a result about 3-connected graphs? Can I learn about polyhedral combinatorics without encountering it or is it something I learn about in a first course?
Reworked the lead with a couple more sources to say something in that direction. —David Eppstein (talk) 17:20, 8 August 2021 (UTC)
Yes, that's the type of things I was looking for. Might be better in a context section in the body, though. (MOS:LEAD says Apart from basic facts, significant information should not appear in the lead if it is not covered in the remainder of the article.)
I think that, other than categorizing what kind of result it is (a classification theorem), the newly added claims (applications in proving other theorems and in graph drawing) all summarize material that can be found in the body of the article. —David Eppstein (talk) 22:15, 8 August 2021 (UTC)
OK, I see your point there.
Some further comments on content (style/presentation to follow later):

History and naming section: This isn't really about history or about naming. "Steinitz submitted a proof in 1916" isn't the entire history of the topic, and the existence of other theorems by Steinitz is more a question of disambiguation here and doesn't tell us since when this particular theorem has been called "Steinitz's theorem".
This was really intended as a disambiguation page, and didn't belong very well in this article. I moved it all to a new separate disambiguation page. The question of who first called it this name is really difficult to sort out in the absence of published sources specifically on that aspect of its history, because of the difficulty of searching pre-internet sources, the likelihood that a fair fraction of those sources will not be in English, the many ways that one could write a phrase equivalent to "Steinitz's theorem", and the difficulty of distinguishing phrases like that intended as descriptive phrases from phrases intended as names. —David Eppstein (talk) 22:46, 8 August 2021 (UTC)
I'm fine with not having a history section and with not discussing the naming unless you can find a book on the history of polyhedral combinatorics. While I'd love to read about the history and the historical context of the proofs, it is probably better to exercise restraint in making any claims of priority etc. here without much better sourcing. Found a history article that you might want to use: Grünbaum, Branko. Graphs of polyhedra; polyhedra as graphs. Discrete Math. 307 (2007), no. 3-5, 445–463. https://mathscinet.ams.org/mathscinet-getitem?mr=2287486
Ok, I'll take a look. —David Eppstein (talk) 23:50, 9 August 2021 (UTC)
Added a brief section on history at the end of the article, based mostly on this reference. —David Eppstein (talk) 00:30, 10 August 2021 (UTC)
That covers what I think are the main points (original proof by Steinitz, graph theory by Grünbaum).
Proof: Is it worth explaining when the other proofs were found? Epifanov and Truemper are mentioned by name (without year), but "Lifting" and "Circle packing" do not mention any names or years.
Note that the part about Epifanov does not claim that Epifanov found the application of his reducibility theorem to polyhedra. That may have come later. The paper is in Russian at http://mi.mathnet.ru/dan31994 if you can read it (I can't), but the MR and zbl reviews describe it as purely about graphs, not polyhedra. Truemper credits Grünbaum for the application of this result to Steinitz's theorem. The history of the circle packing theorem is also complicated, and really belongs to that article rather than here. —David Eppstein (talk) 22:50, 8 August 2021 (UTC)
I can't read Russian, but I can read Cyrillic (I'm something like ru-0.5). Can't see any mention of Steinitz in there.
The German Wikipedia tells me that Steinitz himself gave three proofs in a 1934 book with Rademacher. Are these the same proofs that you show here?
I'm not familiar with that book and also don't read German but I strongly suspect it's three variations of induction proofs, rather than the three approaches (induction, lifting, and circle packing) described in this article. In particular the lifting proof depends heavily on the work of Tutte 1963 and would not be found in a 1934 publication. Similarly, I think the first work on circle packing was Koebe 1936. —David Eppstein (talk) 23:06, 8 August 2021 (UTC)
That makes sense. I'll still try to have a look at that book and will report back if I find anything surprising.
It's not written in the language of graph theory, which makes it difficult to read, but as I understand it, these are essentially just different variations of combinatorics/geometry that ultimately lead to an inductive argument. The only thing I'm wondering now is how the Y-Delta and Delta-Y transforms compare to Thomas Kirkman's face-splitting and vertex-splitting.
I don't think there are easy ways to transform the splitting operations into the YDY transformations, or vice versa. For one thing, you can build any planar graph with a linear number of vertex-splitting steps, but there is a nonlinear bound on YDY transformations. Do you have a reference that uses the splitting operations to prove Steinitz's theorem? —David Eppstein (talk) 23:17, 9 August 2021 (UTC)
No, I was just curious. From a casual observation, it looked like a similar type of operation.
Prose and detail comments:

Lead: it's not a 1922 "paper". Better to use "publication".
Fixed. —David Eppstein (talk) 23:24, 9 August 2021 (UTC)
Proofs: 3-connectivity seems intuitively obvious (any vertex connected to only two other vertices should induce a "two-dimensional" piece of the polyhedron?) so maybe comment on at least the idea of the proof in addition to citing it from Balinski? Is the 3-connectivity true under weaker assumptions on the polyhedron than convexity?
It's not true for all non-convex polyhedra, under reasonably restrictive assumptions (topologically spherical, all faces simple polyhedra). It is true if for topologically-spherical polyhedra where pairs of faces to intersect in (empty, single vertex, or single edge) but to some extent that's just making a definition and then saying that it implies a slightly-rewritten version of itself. I swapped out the image of a non-convex polyhedron with a new one that shows some non-3-connected graphs. I also added a one-sentence summary of the proof of Balinski's theorem. —David Eppstein (talk) 23:17, 9 August 2021 (UTC)
OK, so my intuition was wrong, that's always helpful to know. I like the new image (in "Related results").
Induction: As Steinitz's (you say "Steinitz'" here, which I like, but I think the MOS likes "Steinitz's") proof uses very different (combinatorial, not graph-theoretical) language, you should probably cite the description of this proof to a modern source.
Ok, cited Grünbaum instead. —David Eppstein (talk) 23:24, 9 August 2021 (UTC)
Induction section: The wye-delta article you link to is mostly about electric circuits, with the graph theory hidden deeply inside it. I'm not sure you need to change anything in the present article (you could potentially link to the very short "graph theory" section).
We don't have a separate article to link to on graph-theoretic formulations of Y-Δ transforms (maybe we should). Also related are Apex graph#YΔY-reducibility and Petersen family but I don't think they would be helpful as links here. —David Eppstein (talk) 05:20, 12 August 2021 (UTC)
You could also mention here again that the original proof was not written in the language of graph theory.
Done. —David Eppstein (talk) 05:20, 12 August 2021 (UTC)
Ω(n^3/2): jargon without a link. (Big_O_notation#The_Knuth_definition). But the "sometimes" essentially implies you mean the liminf is large.
Rewritten to avoid Omega-notation and "sometimes". Yes, more or less, but I think liminf is an unnecessarily technical way of expressing it. —David Eppstein (talk) 05:20, 12 August 2021 (UTC)
the degree-two vertices that might be performed by this removal performed?
Fixed. —David Eppstein (talk) 05:20, 12 August 2021 (UTC)
Lifting: each vertex is in the position given by the weighted sum of its neighbors sum->average? Or do you prefer "sum" because average sounds too much like positive weights / convex combination?
I guess average is more accurate, as the image shows a stress where the weights don't add to one. Changed. —David Eppstein (talk) 19:04, 12 August 2021 (UTC)
A picture of the frustrum that belongs to this graph could be nice, but only if it doesn't overwhelm the article.
Added. —David Eppstein (talk) 19:04, 12 August 2021 (UTC)
Consider splitting the final sentence of the Lifting section. I don't quite understand what you say about the "incremental method" and the "a liftable planar drawing that does not have equal weights for all the interior edges": is it a good or a bad thing that we do not have equal weights?
Split long sentence and removed the part about the incremental method. I was under the impression that it allows more general outer faces, but it doesn't (only triangles). Really that reference is about a point from later in the article, on realizations with well-separated vertices and linear volume. —David Eppstein (talk) 19:04, 12 August 2021 (UTC)
Circle packing: Looks good.
Integer coordinates: Source for doubly exponential is a blog, not superb. What does the "graph drawing" reference say?
It only gives a single-exponential lower bound, not the double-exponential upper bound stated here. But Onn and Sturmfels also state the double-exponential upper bound, so I replaced the blog source by reusing that source. —David Eppstein (talk) 19:52, 12 August 2021 (UTC)
Equal slopes: As I understand it, this is an extra property that we get only under (much?) stronger assumptions on the type of graph. Are there other graphs than Halin graphs that have equal slope representation?
I think that such a representation necessarily comes from lifting a straight skeleton of a convex polygon and therefore necessarily comes from a Halin graph. Intuitively, one can't introduce new equal-slope faces higher up than the base because the edge they'd replace is already lower than that slope. But that's not a proof and I don't know of a source that explicitly says that (Incidentally, the Aichholzer et al source that we're using for this part is phrased in terms of trees and straight skeletons, not Halin graphs and polyhedra. The correspondence between straight skeletons and equal-slope polyhedral surfaces can be found in plenty of other sources. The equal-slope realization of Halin graphs is stated more explicitly in my paper "Treetopes and their graphs", credited to Aichholzer et al., but out of modesty I didn't add it as a source here. I can add it if you think I should.) —David Eppstein (talk) 19:52, 12 August 2021 (UTC)
I think what I'm looking for is a clearer statement linking the Halin graphs with the rest of the result. Basically, make it clear also for the less observant reader that Halin graphs are a special subclass of 3-connected plane graphs, and Steinitz's theorem for these graphs can be strengthened by asking for equal slopes.
Done. —David Eppstein (talk) 19:22, 13 August 2021 (UTC)
Circle packing theorem: I don't like the links to Koebe and Thurston (and not to Andreev) very much, do you need them here?
Agreed. If anywhere, those names belong in the earlier circle packing section or the history section (where I have moved them), not here. —David Eppstein (talk) 01:37, 13 August 2021 (UTC)
Good choice.
The characterization involves edge weights, constrained by systems of linear inequalities. I don't quite know what is happening here.
Rewritten in an attempt to clarify this. —David Eppstein (talk) 02:13, 13 August 2021 (UTC)
It is a lot less mysterious now.
Related results: "algorithmic Steinitz problem" could be italic as a definition? (I think there's some more like that). Or do we not do that here?
Done. —David Eppstein (talk) 19:22, 13 August 2021 (UTC)
It is complete: Can you make it clearer (also to readers not clicking the link) that you are talking about complexity theory? Or explain in layman's (well, semi-layman's) terms what "complete for the existential theory of the reals" means?
Done. —David Eppstein (talk) 19:22, 13 August 2021 (UTC)
Could you explain more what Lovasz's theorem is?
Done. —David Eppstein (talk) 05:54, 14 August 2021 (UTC)
History: "cryptic", well, it's only cryptic if you expect graph theory I guess.
"Cryptic" was intended less to be about the fact that it was written in a different formalism, and more as a summary of Grünbaum's "The difficult chore of deciphering what this means is probably responsible for the long-lasting ignorance of this basic theorem about convex polyhedra. ... The formulation of Steinitz’s criteria is quite cumbersome." —David Eppstein (talk) 01:06, 13 August 2021 (UTC)
OK.
It's a very nice article overall. I'll leave you with my comments for now and will do a second pass then, but I don't think it will take much longer. —Kusma (talk) 16:09, 10 August 2021 (UTC)

Nice improvements. I hope I wasn't asking for something impossible with the Lovasz question. I found one other issue in your history edits: the Steiner reference doesn't look right. The publisher of the 1896 (not 1832) edition you link to isn't Fincke, but Wilhelm Engelmann in Leipzig. Also, the actual statement is not in the thing you link to, but in the second part, p. 144, question 77.
After writing the above, I found the actual 1832 Fincke edition: [1], where it is p. 316. Cite what you like, but don't mix them up. —Kusma (talk) 21:34, 13 August 2021 (UTC)


### Table
Should the statement of Steinitz Theorem specify a simple graph? See for example Lectures on Polytopes by Gunter Ziegler. Greenlinda (talk) 21:03, 25 August 2022 (UTC)

If we're being pedantic, we need to specify that we are talking about finite simple undirected 3-vertex-connected planar graphs. This might be appropriate in the "definitions" section. In the lead, clarity is more important than pedantry. —David Eppstein (talk) 00:06, 26 August 2022 (UTC)
I only asked because, as a novice to graph theory, I spent about 10 minutes confused by this before asking a friend, wondering, for example, if simple might be part of the definition of 3-vertex connected, while I did not hesitate to assume that the graphs were finite and undirected. But I understand the balance between brevity / clarity and completeness. Thanks for the article! Greenlinda (talk) 23:08, 26 August 2022 (UTC)