Talk:Graph embedding

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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

• The connection between surfaces and graph minors as given by the Graph Structure Theorem

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

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

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 41.5.196.11 (talk) 11:26, 14 December 2011 (UTC)Reply

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

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

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

Currently the definition requires an embedding to map into a compact, connected space. The compactness restriction seems rather odd, because it is often desirable to talk about embeddings on non-compact spaces such as the next two examples provided by this very article, ${\displaystyle \mathbb {R} ^{3}}$ and ${\displaystyle \mathbb {R} ^{2}}$. I am aware that ${\displaystyle \mathbb {R} ^{3}}$ is an edge case and planarity can be defined in terms of spherical embeddings making reference to ${\displaystyle \mathbb {R} ^{2}}$ not strictly necessary, however I just don't see any reason to restrict the manifold so much. The definition works perfectly well for just manifolds. Compactness is stated without citation and doesn't appear elsewhere in the article so unless someone can find an author that requires compactness, i.e. provide a citation, I plan on removing it. AquitaneHungerForce (talk) 08:44, 2 August 2022 (UTC)Reply

I take slight issue with this article claiming the whole term "graph embedding" for embeddings into surfaces. There are many other situations where a graph is "embedded" in some high dimensional space. I can think of spectral graph embeddings, nullspace embeddings, Colin de Verdière embeddings, 1-skeleta of polytopes, spacial graphs (in knot theory) etc. Some of these take the embedding part (i.e. injectivity) not always super serious, but they are established terminology nevertheless. Currently it feels weird to say, e.g., that a polytope skeleton is an embedding of its edge graph, because I cannot link to what a graph embedding is. I am thinking about how to solve this (including the more general definition in this article; splitting off parts of this article; disambiguation; etc.). Any suggestions? MWinter4 (talk) 22:20, 1 September 2023 (UTC)Reply

This article is really about a specific concept rather than the term "graph embedding" (WP:NOTADICTIONARY). The solution here is to link to the relevant article for the concept, and if there is real chance of a reader getting confused add a hatnote (e.g. {{Redirect}}, {{About}}). That being said it's a little hard for me to imagine what you want to link to when you say the 1-skeleton is a embedding of its edge graph, since I don't really understand what it is trying to say. The abstract structure of the 1-skeleton is the edge graph, but I'm not sure what beyond that there is to be said. What's interesting about this realization of the skeleton? AquitaneHungerForce (talk) 01:15, 2 September 2023 (UTC)Reply