Editing Planar graph (section)

==Generalizations==
An [[apex graph]] is a graph that may be made planar by the removal of one vertex, and a ''k''-apex graph is a graph that may be made planar by the removal of at most ''k'' vertices.

A [[1-planar graph]] is a graph that may be drawn in the plane with at most one simple crossing per edge, and a ''k''-planar graph is a graph that may be drawn with at most ''k'' simple crossings per edge.

A [[map graph]] is a graph formed from a set of finitely many simply-connected interior-disjoint regions in the plane by connecting two regions when they share at least one boundary point. When at most three regions meet at a point, the result is a planar graph, but when four or more regions meet at a point, the result can be nonplanar (for example, if one thinks of a circle divided into sectors, with the sectors being the regions, then the corresponding map graph is the complete graph as all the sectors have a common boundary point - the centre point).

A [[toroidal graph]] is a graph that can be embedded without crossings on the [[torus]]. More generally, the [[genus (mathematics)|genus]] of a graph is the minimum genus of a two-dimensional surface into which the graph may be embedded; planar graphs have genus zero and nonplanar toroidal graphs have genus one. Every graph can be embedded without crossings into some (orientable, connected) closed two-dimensional surface (sphere with handles) and thus the genus of a graph is well defined. Obviously, if the graph can be embedded without crossings into a (orientable, connected, closed) surface with genus g, it can be embedded without crossings into all (orientable, connected, closed) surfaces with greater or equal genus. There are also other concepts in graph theory that are called "X genus" with "X" some qualifier; in general these differ from the above defined concept of "genus" without any qualifier. Especially the non-orientable genus of a graph (using non-orientable surfaces in its definition) is different for a general graph from the genus of that graph (using orientable surfaces in its definition).

Any graph may be embedded into three-dimensional space without crossings. In fact, any graph can be drawn without crossings in a two plane setup, where two planes are placed on top of each other and the edges are allowed to "jump up" and "drop down" from one plane to the other at any place (not just at the graph vertexes) so that the edges can avoid intersections with other edges. This can be interpreted as saying that it is possible to make any electrical conductor network with a two-sided [[circuit board]] where electrical connection between the sides of the board can be made (as is possible with typical real life circuit boards, with the electrical connections on the top side of the board achieved through pieces of wire and at the bottom side by tracks of copper constructed on to the board itself and electrical connection between the sides of the board achieved through drilling holes, passing the wires through the holes and [[soldering]] them into the tracks); one can also interpret this as saying that in order to build any road network, one only needs just bridges or just tunnels, not both (2 levels is enough, 3 is not needed). Also, in three dimensions the question about drawing the graph without crossings is trivial. However, a three-dimensional analogue of the planar graphs is provided by the [[linkless embedding|linklessly embeddable graphs]], graphs that can be embedded into three-dimensional space in such a way that no two cycles are [[linking number|topologically linked]] with each other. In analogy to Kuratowski's and Wagner's characterizations of the planar graphs as being the graphs that do not contain ''K''<sub>5</sub> or ''K''<sub>3,3</sub> as a minor, the linklessly embeddable graphs may be characterized as the graphs that do not contain as a minor any of the seven graphs in the [[Petersen family]]. In analogy to the characterizations of the outerplanar and planar graphs as being the graphs with [[Colin de Verdière graph invariant]] at most two or three, the linklessly embeddable graphs are the graphs that have Colin de Verdière invariant at most four.