Graph embedding: Difference between revisions

Revision as of 08:22, 22 January 2016

Revision as of 18:05, 22 January 2016

Line 5:

Here a surface is a [[compact space|compact]], [[connected space|connected]] 2-[[manifold]].

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. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space <math>\mathbb{R}^3</math><ref name="3d-gd">{{citation

| last1 = Cohen | first1 = Robert F.

| last2 = Eades | first2 = Peter | author2-link = Peter Eades

Line 55:

==Embeddings of graphs into higher-dimensional spaces==

It is known that any finite graph can be embedded into a three-dimensional space.<ref name="3d-gd"/>

One method for doing this is to place the points on any line in space and to draw the{{Clarify|reason=what 'm' edges? - see talk page}} ''m'' edges as curves each of which lies in one of ''m''a distinct [[halfplane]]s, with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a [[book embedding]] of the graph. This [[metaphor]] comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page"; the ''book thickness'' of the graph is the minimum number of halfplanes needed for such a drawing.

Alternatively, any finite graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in [[general position]] so that no four are coplanar. For instance, this may be achieved by placing the ''i''th vertex at the point (''i'',''i''²,''i''³) of the [[moment curve]].

An embedding of a graph into three-dimensional space in which no two of the cycles are topologically linked is called a [[linkless embedding]]. A graph has a linkless embedding if and only if it does not have one of the seven graphs of the [[Petersen family]] as a [[minor (graph theory)|minor]].