Talk:Book embedding

Arc diagrams

In See also Arc diagrams are referred to as two-page book embeddings. In Arc diagram#Planar graphs it is discussed how some planar graphs can only be represented as topological two-page book embeddings. I propose this be expanded upon in this article.

67.252.103.23 (talk) 15:42, 11 June 2014 (UTC)

Yes, I'm working on expanding this article and intend to add a section here within the next few days on graph visualization applications of book embeddings. But note that the image you link above is *not* a book embedding, because one of its edges crosses from one page to another. —David Eppstein (talk) 15:48, 11 June 2014 (UTC)

I included it as an example of a topological book embedding, which is the section that I proposed needed expansion/disambiguation. 67.252.103.23 (talk) — Preceding undated comment added 16:32, 11 June 2014 (UTC)

Question: minor-closed families

I am confused by this statement:

"All minor-closed graph families, and in particular the graphs with bounded treewidth or bounded genus, also have bounded book thickness."

Consider the set of all graphs. As far as I understood the linked article and also this article, this set is minor-closed. But because this set also contains all complete graphs, it has an unbounded book thickness.

Am I making a mistake somewhere?

Does this sentence only apply to all other minor-closed graph families? If so, I propose to mention this.

Baum42 (talk) 11:02, 12 June 2015 (UTC)

Yes, all nontrivial minor-closed graph families. That one is an exception to most statements about minor-closed families. —David Eppstein (talk) 17:32, 12 June 2015 (UTC)

GA Review

This review is transcluded from Talk:Book embedding/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Cryptic C62 (talk · contribs) 15:50, 4 April 2016 (UTC)

Again, this article is off to an excellent start. I am particularly impressed with the efforts to summarize esoteric concepts in layman's terms, something deemed largely impossible by the mathematicians I have met. Comments through Behavior under subdivisions:

• "with or without knowing a fixed vertex ordering along the spine of the book." The term spine has not yet been defined, which should probably happen in the first paragraph.
• "It is unknown whether the book thickness of arbitrary graphs can be bounded by a function of the book thickness of their subdivisions." I think this would be slightly clearer in the singular rather than the plural: "It is unknown whether the book thickness of an arbitrary graph can be bounded by a function of the book thickness of its subdivision." This avoids any ambiguity about whether a single graph can have multiple subdivisions.
• The History section ends with a one-sentence paragraph, causing sadness. Happiness could result from expanding the paragraph or merging it.
• "it is the maximum size of a subset of edges within a single spine such that the intervals defined on the spine by pairs of endpoints of the edges all intersect each other." Perhaps I have misunderstood this concept, but I believe the highlighted word spine should be replaced with page, correct?
• I think the Definitions section would greatly benefit from the addition of diagrams, particularly for book crossing number and pagewidth.
  •  Done —David Eppstein (talk) 00:49, 16 April 2016 (UTC)
• "The two-page crossing number of the complete graph K_n is" Perhaps this should start a new paragraph to avoid confusion.
• In Specific Graphs, are there any results for multipartite graphs?
• "(but with only one copy of each vertex that appears more than once on the outer face)" I find this comment confusing. How could a vertex appear more than once?
• In the last paragraph of Relation to other graph invariants, the discussion of the stack data structure makes sense to me, but I really don't understand the connection to the queue data structure. I think an additional sentence of explanation would go a long way.
  •  Done Rewritten, I hope more clearly. —David Eppstein (talk) 00:15, 16 April 2016 (UTC)
• "However, this model does not apply to more sophisticated traffic controllers that do not operate in a fixed sequence of phases."
  •  Done It's too difficult to source a negative, so I just removed this caveat. —David Eppstein (talk) 00:15, 16 April 2016 (UTC)

Done! --Cryptic C62 · Talk 15:51, 13 April 2016 (UTC)

Thanks, and please let me know when you finish. I'm still completing revisions to the other GA nom for linear probing, and then traveling next week, but should have time to work on this after that. —David Eppstein (talk) 06:08, 6 April 2016 (UTC)

In the meantime I think I've handled all of these comments except for the request for diagrams and the request for additional results about multipartite graphs. (It's not that I don't want to do those, too, only that they're not done yet.) —David Eppstein (talk) 23:31, 8 April 2016 (UTC)

Multipartite graphs added. —David Eppstein (talk) 18:56, 10 April 2016 (UTC)

I have now commented on the entire article. I also made a few tweaks myself, which you are welcome to review. --Cryptic C62 · Talk 15:51, 13 April 2016 (UTC)

Ok, I think I have now addressed all your comments. (And thanks for the tweaks.) —David Eppstein (talk) 00:49, 16 April 2016 (UTC)

Great success! I have passed the article. I especially like the new diagrams. They definitely help to solidify the more abstract definitions. --Cryptic C62 · Talk 20:19, 17 April 2016 (UTC)

Blankenship–Oporowski conjecture disproven

I'm not adding this to this article or to List of unsolved problems in mathematics, at least not until it's been properly peer-reviewed and published, but https://arxiv.org/abs/2011.04195 provides a counterexample to the Blankenship–Oporowski conjecture. —David Eppstein (talk) 02:40, 10 November 2020 (UTC)