Content deleted Content added
m mojibake |
same again |
||
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 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 graph can be embedded into a three-dimensional space.
One method for doing this is to place the points on any line in space and to draw the ''m'' edges as curves each of which lies in one of ''m'' distinct [[halfplane]]s 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.
| |||