# Talk:Halin graph

Hello,
This article, together with Wolfram and other sources, defines roofless polyhedron as a synonym for Halin Graph. However this book restricts the roofless polyhedra (aka based polyhedra) to the subclass of Halin graphs that are cubic.
Who is correct? --MathsPoetry (talk) 10:26, 12 January 2013 (UTC)

Unfortunately, Google won't show me the page you link to. —David Eppstein (talk) 16:56, 12 January 2013 (UTC)
That's weird, it works perfectly here. Here is a screenshot of that page, valid 7 days from now. --MathsPoetry (talk) 17:27, 12 January 2013 (UTC)
Ok, that appears to be MR 0351915, which indeed says that the roofless polyhedra are the 3-regular Halin graphs. But the reference in the article now (MR 0707063) clearly says that roofless polyhedra and Halin graphs are the same as each other, as do MR 0831866 and MR 1221567. (Note that the last one shares an author with the reference you found.) That's all I can find that mention roofless polyhedra in Google scholar or MathSciNet  (I don't consider non-scholarly web sources as helpful for this sort of subject). Maybe rather than picking one we should say that sometimes "roofless polyhedron" is used as a synonym for a Halin graph and sometimes it is used to mean a 3-regular Halin graph, with sources for both meanings? Also, some of these references mention early work on these graphs by Rademacher and Polya (possibly independent from Halin?) that would probably be worthwhile to track down. —David Eppstein (talk) 19:59, 12 January 2013 (UTC)
My turn to be unable to follow the links that you mention. Anyway, I agree with the individual solutions that you propose. Currently, I just didn't translate the English version to French, in the expectation that you would sort this out in the English article. Best, --MathsPoetry (talk) 20:56, 12 January 2013 (UTC)
Sorry about that. Two of those links are the reference that was already in the article and the one you found (that is now in the article). The other two are Cornuéjols, G.; Naddef, D.; Pulleyblank, W. (1985), "The traveling salesman problem in graphs with 3-edge cutsets", Journal of the Association for Computing Machinery, 32 (2): 383–410, doi:10.1145/3149.3154, MR 0831866 and Holton, D.; Plummer, M. D. (1988), "2-extendability in 3-polytopes", Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, Amsterdam: North-Holland, pp. 281–300, MR 1221567. —David Eppstein (talk) 21:31, 12 January 2013 (UTC)
I'm still unable to read more than abstracts or first pages. Science not being free is a real problem. Anyway, I trust you, and I'm fine with the new formulation. Thanks. Ah, what about a mention of the term based polyhedra? Also, feel free to use new illustration above. --MathsPoetry (talk) 21:39, 12 January 2013 (UTC)
I put the term "based polyhedra" into a new "History" section, which also traces these graphs over 100 years prior to Halin, in the work of Kirkman. —David Eppstein (talk) 22:07, 12 January 2013 (UTC)
Cool! Suggestion: move the sentence about the term roofless polyhedra to the history section as well, while developping where this other term comes from. --MathsPoetry (talk) 22:10, 12 January 2013 (UTC)

"for every edge in the graph, the removal of that edge reduces the connectivity of the graph". Why is this mentioned? Especially that being 3-vertex-connected is about connectivity when removing vertices, not edges. Was it Halin's point? If yes it should be mentioned, IMHO. --MathsPoetry (talk) 22:51, 13 January 2013 (UTC)

It was Halin's point. It is not true of all graphs: some graphs have redundant edges, the removal of which doesn't change the connectivity. Halin graphs don't. —David Eppstein (talk) 23:40, 13 January 2013 (UTC)
Thank you very much for the clarification. --MathsPoetry (talk) 18:30, 14 January 2013 (UTC)

Maybe I did not search well, but I was unable to get a clear idea of what an "embedding" was, for example from the article about trees. Would it be possible to give a definition, a good internal link or a word of explanation? Sorry in advance if I missed some obvious solution. --MathsPoetry (talk) 21:45, 12 January 2013 (UTC)

It means that you draw it in the plane without crossings. The same tree may have multiple drawings, which give rise to different Halin graphs. —David Eppstein (talk) 20:56, 14 January 2013 (UTC)
OK, I now get the idea more or less precisely the idea of the "unique embedding". Do we have a page that explains precisely this idea of embedding for graphs, and that we could point to in a blue link? --MathsPoetry (talk) 15:27, 18 January 2013 (UTC)
Answering to myself: simply graph embedding . Adding the blue link... --MathsPoetry (talk) 15:29, 18 January 2013 (UTC)

An article in Wikipediocracy calls this article "semi-literate at best", and I can see what they mean: I had to read the first sentence a few times before I could make sense of it. I have boldly substituted a simpler wording. I hope it meets with approval. RockMagnetist (talk) 23:25, 14 November 2013 (UTC)
I like the improvements by David Eppstein. I admit, I was a little timid in reducing the jargon, because this isn't my field. RockMagnetist (talk) 02:06, 15 November 2013 (UTC)

But if it isn't your field, you're probably better equipped to recognize which parts are too jargony. And thanks. It's good motivation to see something one has worked on extensively already put down as "semi-literate". —David Eppstein (talk) 02:18, 15 November 2013 (UTC)
Yes, that's got to sting! RockMagnetist (talk) 02:19, 15 November 2013 (UTC)

In first section I read: "has at least four vertices"
In section "Construction" I read: "with at least three vertices"
I think second is wrong. Jumpow (talk) 10:38, 21 December 2013 (UTC)Jumpow

 Fixed — Probably a confusion between "at least" and "more than" D.Lazard (talk) 11:39, 21 December 2013 (UTC)
I don't think it was actually incorrect before, just misleading (there is no tree with exactly three vertices and no degree-two vertices, so saying that it's at least three and that it's at least four are equivalent). Anyway, the change is an improvement. —David Eppstein (talk) 16:51, 21 December 2013 (UTC)

Hello fellow Wikipedians,
I have just modified 2 external links on Halin graph. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

Added archive https://web.archive.org/web/20040728112030/http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf to http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf
Added archive https://web.archive.org/web/20081211092401/http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_198.html to http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_198.html
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—InternetArchiveBot (Report bug) 10:38, 28 October 2017 (UTC)

This review is transcluded from Talk:Halin graph/GA1. The edit link for this section can be used to add comments to the review.
Reviewer: Some Dude From North Carolina (talk · contribs) 01:21, 18 July 2021 (UTC)

Add a short description and then WP:ALT text for every image.
I don't really see the point of alt texts that duplicate the information in the image captions, and Wikipedia:Manual of Style/Accessibility/Alternative text for images agrees, while saying that for technical reasons the alt texts should not actually be missing or blank. Anyway, ok, done. —David Eppstein (talk) 20:16, 18 July 2021 (UTC)
"remains Hamiltonian after deletion of" → "remains a Hamiltonian after the deletion of"
No. That would be ungrammatical. Correct grammar would be either "remains [adjective] after ..." or "remains [noun phrase] after ...". "Hamiltonian" is correct, as an adjective. "a Hamiltonian" is incomplete as a noun phrase: a Hamiltonian what? (It is possible to use "a Hamiltonian" as a noun in mathematics but it means something unrelated.) —David Eppstein (talk) 20:16, 18 July 2021 (UTC)
Thoughts on adding "the" before "deletion"? Some Dude From North Carolina (talk) 00:49, 19 July 2021 (UTC)
Non-problematic. Done. —David Eppstein (talk) 01:25, 19 July 2021 (UTC)
Remove the comma after "the application of Courcelle's theorem".
This is from a sentence "Other methods include [method 1], or [method 2], neither of which...". The comma is optional but not incorrect. It serves a useful purpose in this sentence, preventing "the application of Courcelle's theorem or a method based on graph rewriting" from being misread as a single method described in two ways. —David Eppstein (talk) 20:16, 18 July 2021 (UTC)
"These graphs gained in significance" → "These graphs gained significance"
Done. —David Eppstein (talk) 20:16, 18 July 2021 (UTC)
The second paragraph in #History needs a source.
Extended the footnote to Rademacher to cover the part stated in his work, and repeated a different footnote to source the claim that his work is about Halin graphs. Done. —David Eppstein (talk) 20:22, 18 July 2021 (UTC)
That's it. Great work on this article. 

@David Eppstein. The article mentions something about polyhedron, but does this article has an illustration of it? Dedhert.Jr (talk) 17:26, 9 November 2024 (UTC)