Talk:Graph embedding

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field:  Discrete mathematics

Important results?[edit]

What are the most significative results about graph embedding (in other surface than the plane) ?

I am not sure who asked this question, but here two "significant results" that might be mentioned.
* Carsten Thomassen's "5-color theorem":
For any surface, there exists an integer k such that every loopless graph embedded on that surface with edge-width at least k is properly 5-colorable. The edge-width of a graph is the least length of a cycle C in the graph such that C is not a contractible curve on the surface (that is, C is homotopically nontrivial, or equivalently, C does not bound a disc on on the surface).

Luis Goddyn (talk) 18:50, 4 February 2009 (UTC)


this page could probably do with being reorganized, the layout is kind of messy, and we could probably put some pictures in too. Genusfour (talk) 12:37, 2 September 2009 (UTC)


In the opening paragraph the author writes "Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints." I don't agree with this statement. This seems more like the definition of a "planar graph embedding". A graph embedding in dimension d is simply an assignment d-dimensional coordinates to vertices of the graph. A planar graph embedding is a graph embedding where edges only intersect at their endpoints. — Preceding unsigned comment added by (talk) 11:26, 14 December 2011 (UTC)

Assigning coordinates to the vertices is not enough to specify where the edges go — they need not be straight. And "in dimension d" is very much not the same thing as "into a surface". —David Eppstein (talk) 17:11, 14 December 2011 (UTC)
I have seen in the litterature embeddings in pretty much anything, including spaces of dimension 1, 3, 4 and higher. See for example the chapter "Graph dimension" in the book "the mathematical colouring book" of Alexander Soifer. Dimensions higher than 2 make sense if you add additional constraints to the graph. I have the impression that "surface" should be replaced with something less restrictive than dimension 2. --MathsPoetry (talk) 21:24, 9 May 2013 (UTC)

m edges?[edit]

I marked a claim about m edges as "clarification needed" ({{Clarify}}) since it seems to me that the article is talking about any graph, in which case the number of edges could be infinite. Presumably book embeddings work fine for infinite graphs, you just might need an infinite number of pages. But then, why talk about m edges? Arided (talk) 08:12, 22 January 2016 (UTC)