Talk:Halin graph

Roofless polyhedra

A triangular prism seen as a Halin graph (tree in blue, cycle in black), in case it helps.

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 MR0351915, which indeed says that the roofless polyhedra are the 3-regular Halin graphs. But the reference in the article now (MR0707063) clearly says that roofless polyhedra and Halin graphs are the same as each other, as do MR0831866 and MR1221567. (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)

Purpose of remark?

"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)

Embedding

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)

More literate wording?

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)

There is controversy in article

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)

External links modified

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: 18 January 2022).

• 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)

GA Review

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.

GA review (see here for what the criteria are, and here for what they are not)
It is reasonably well written. a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists): It is factually accurate and verifiable. a (references): b (citations to reliable sources): c (OR): d (copyvio and plagiarism): It is broad in its coverage. a (major aspects): b (focused): It follows the neutral point of view policy. Fair representation without bias: It is stable. No edit wars, etc.: It is illustrated by images, where possible and appropriate. a (images are tagged and non-free images have fair use rationales): b (appropriate use with suitable captions):
Overall: Pass/Fail:
· · ·

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Desertarun (talk) 15:15, 1 August 2021 (UTC)

(

• Comment or view
• Article history

)

• ... that when a tree is a star, connecting its leaves in a cycle makes a wheel? Source: Cornuéjols et al (1983), Halin graphs and the travelling salesman problem: "If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph."
  • ALT1:... that many hard combinatorial optimization problems are easier on Halin graphs because of their low treewidth? Source: Bodlaender (1988), Dynamic programming on graphs with bounded treewidth: "we show for a large number of graph decision problems ... the existence of O(n^C) or polynomial algorithms for these problems, restricted to the graphs with bounded treewidth"

• Reviewed: Sacred Heart of Jesus (Batoni)

Improved to Good Article status by David Eppstein (talk). Self-nominated at 00:39, 21 July 2021 (UTC).

General: Article is new enough and long enough
New enough: Long enough:

Policy: Article is sourced, neutral, and free of copyright problems
Adequate sourcing: Neutral: Free of copyright violations, plagiarism, and close paraphrasing:

Hook: Hook has been verified by provided inline citation
Cited: Interesting:

QPQ: Done.

Overall: Long enough, new enough, well sourced, neutral, no copyvio. Both the hook and the article itself are really interesting. Ready to go! Zin Win Hlaing (talk) 04:09, 24 July 2021 (UTC)