Talk:Halin graph

File:Triangular prism as halin graph.svg

Hello,

This article, together with Wolfram and other sources, defines roofless polyhedron as a synonym for Halin Graph. However [http://books.google.fr/books?id=Ehw4AAAAIAAJ&pg=PA104&lpg=PA104 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. [http://picpaste.com/halin-OS5piIUt.png 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 {{citation

| last1 = Cornuéjols | first1 = G.

| last2 = Naddef | first2 = D.

| last3 = Pulleyblank | first3 = W.

| doi = 10.1145/3149.3154

| issue = 2

| journal = Journal of the Association for Computing Machinery

| mr = 831866

| pages = 383–410

| title = The traveling salesman problem in graphs with 3-edge cutsets

| volume = 32

| year = 1985}} and {{citation

| last1 = Holton | first1 = D.

| last2 = Plummer | first2 = M. D.

| contribution = 2-extendability in 3-polytopes

| location = Amsterdam

| mr = 1221567

| pages = 281–300

| publisher = North-Holland

| series = Colloq. Math. Soc. János Bolyai

| title = Combinatorics (Eger, 1987)

| volume = 52

| year = 1988}}. —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 {{smiley}}. Adding the blue link... --MathsPoetry (talk) 15:29, 18 January 2013 (UTC)

An [http://wikipediocracy.com/2013/10/20/elementary-mathematics-on-wikipedia-2/#comment-28166 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

:{{corrected}} — 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 [https://en.wikipedia.org/w/index.php?diff=prev&oldid=807499441 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.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—InternetArchiveBot (Report bug) 10:38, 28 October 2017 (UTC)

{{Talk:Halin graph/GA1}}

{{Did you know nominations/Halin graph}}

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