This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; algebra) that generalize the notion of planar graphs, and how properties of planar graphs extend in these wider contexts.

I guess one possible generalization could be: an $m$dimensional stratified space (i.e. "manifold with singularities") which is embeddable in $2m$dimensional Euclidean space. Every smooth manifold can be so embedded (by Whitney's theorem), but singularities may force the ambient dimension higher, as witnessed by the simple case $m=1$ in which "stratified space" is just a graph and the embeddability condition is just planarity. (This was just invented on the spot  I have no idea if this is actually an interesting definition...) 


There are many generalizations, but one of my favorites is "neighborhood systems": intersection graphs of systems of balls in a Euclidean space of bounded dimension, with the property that any point of the space is covered by a bounded number of balls. If the dimension is two and the number of balls covering any point is at most two, these are exactly the planar graphs (KoebeThurstonAndreev), they have at most a linear number of edges in any dimension, and more importantly from the point of view of divideandconquer algorithms they have separator theorems in any dimension (ShangHua Teng and others). 


Some of the broadest generalizations generalize the family of planar graphs. Possibly the most important generalization along these lines is the notion of a minorclosed graph family, among which the planar graphs are apparently again quite exceptional in a way I don't pretend to understand. 


The plane can be generalized to surface of higher genus. Also although any graph can be embedded in a higher dimensional space perhaps a hypergraph could not. I think this could be generalized further to embedding hypergraphs in various higher dimensional manifolds 


Planar graphs can be characterized in terms of various minor monotone graph invariants such as $\mu(G)$ of Colin de Verdière, or the recent $\sigma(G)$ of Van der Holst and Pendavingh. A graph $G$ is planar if and only if $\mu(G)$, or $\sigma(G)\leq 3$. You can relax this to $\leq 4$, which turns out to be the flat graphs $G$, those that are linklessly embeddable in 3space. A linkless embedding can be found in polynomial time (Van der Holst) (checking planarity is linear  Hopcroft and Tarjan). There are many connections to linear algebra, topology, and combinatorial geometry. Also, since $\mu(G)\leq 2$ if and only if $\sigma(G)\leq 2$ if and only if $G$ is outerplanar, outerplanarity can be considered to be a natural strengthening of planarity (which goes in the opposite direction from that asked by the question). Note: There is also a $\lambda(G)$ of Van der Holst, Laurent and Schrijver (paper) which does not characterize planarity. Instead, $\lambda(G)\leq 3$ iff $G$ does not have $K_5$ or a certain graph $V_8$ as minor. 


Planar graphs have a linear number of edges in terms of the number of vertices that the graph has. One can attempt to find "geometric conditions" on a graph so that it has a linear number of edges in terms of the number of its vertices. One such result is: Quasiplanar graphs have a linear number of edges http://www.springerlink.com/content/v276423723348224/ Joe Malkevitch 


One interesting generalization is to "small classes of graphs." A class of graphs is small if the number of isomorphism classes of such graphs with n vertices is (only) exp (O(n)). Forests, planar graphs, minorclosed families (which avoid some graph), graphs of simple dpolytopes for a fixed d, are all known to be small. (I am not sure about the later case if you include also all subgraphs of these graphs; also it is not known if the class of dual graphs of triangulated dspeheres is small, for d>= 3). The class of cubic graphs is not small. One way to prove that an hereditary class of graphs (namely a class of graphs closed under taking subgraphs) is small is via a seperator's theorem. Suppose that every graph in the class with n vertices can be separated by a set of g(n) vertices to connected components of size at most 2/3n. Then if g(n) is smaller than n/(log n)^2 it is sufficient to demonstrate that the class is small. (There are examples where g(n)=n/(log n)^0.99, so that the class is not small and it is an open problem to find the right exponent of logn that guarantees that the class is small.) For graphs with a forbidden minor it is known that g(n)=C sqrt n is enough. (I do not know if graphs of simple dpolytopes have a seperation theorem.) 


Another possibility is a family of concepts related to thickness: the minimum number of colors one needs to color the edges in a drawing of the graph in the plane such that edges of the same color do not cross. Planar graphs are graphs with thickness one, and the natural generalizations are to graphs of bounded thickness. For thickness, the drawing is allowed to have curved edges; if the edges are straight ("geometric thickness") one gets a somewhat more restricted class of graphs, and "book thickness" or "pagenumber" (the vertices are on a line and the edges are curves within a single halfplane bounded by that line) is more restrictive still. 


Ooh, this is another "off the top of my head" one, but another generalization of the family of planar graphs is matroid families closed under taking duals. 


Graphs which are stressfree for a generic embedding into space is an interesting class of graphs that includes all planar graphs. One thing to notice is that edges of maximal planar graphs with n vertices do not form the set of bases of a matroid. (Still maximal planar graphs have one pleasant property of matroids that they all have the same number of edges 3n6.) There are related matroids defined on edge sets of complete graphs on n vertices: the most well known is the matroid described by generic rigidity of spacial embeddings. Gluck proved that planar graphs are generically 3rigid, and this result is based on DehnAlexandrov's theorem asserting that (embedded) graphs of simplicial 3polytopes are infinitesimally rigid. 


I think it is worth noting that circle graphs can be seen as a generalization of planar graphs. Circle graphs are intersection graphs of chords in a chord diagram. In 1981, de Fraysseix showed that a bipartite graph is a circle graph if and only if it is a fundamental graph of a PLANAR graph. (The fundamental graph of a graph G with respect to its spanning tree T is the bipartite graph on E(G) such that an edge e in T and another edge f not in T are adjacent if and only if Tf+e is a tree.) There is even a Kuratowskitype theorem for characterizing circle graphs, which actually implies the Kuratowski theorem for planar graphs. http://dx.doi.org/10.1002/jgt.v61:1 


Jarik Nesetril and Patrice Ossona de Mendez developed the notion of "nowhere dense graphs" which extends the class of planar graphs. The class of nowhere dense graphs include all graphs with a forbidden minor; all graphs of bounded degrees but not all $d$degenerate graphs. They are important in graph theory and in logic. 


Here is another generalization of planar graphs. Start with a $d$dimensional polytope $P$ with $n$ vertices. For every $2$dimensional face $F$ triangulate $F$ by non crossing diagonals. So if $F$ has $k$ sides you add $(k3)$ edges. It is known that the total number of edges you get (including the original edges of the polytope) is at least $$dn  {{d+1} \choose {2}}.$$ A polytope is called "elementary" if equality holds. We can consider the following classes of graphs: 1) $E_d$ = Graphs of elementary $d$polytopes and all their subgraphs 2) $F_d$ = Graphs obtained by elementary $d$polytopes by triangulating all $2$faces by non crossing diagonals, and all their subgraphs. For $d=3$ both classes are the class of planar graphs. Some properties of planar graphs are known or conjectured to extend. 1) (robustness; conjectured) We can start instead of polytopes by arbitrary polyhedral (d1)dimensional pseudomanifolds. But it is conjectured that we will get precisely the same class of graphs. 2) (duality; known) If $P$ is elementary so is its dual $P^*$, 3) (coloring; conjectured) Graphs in $E_d$ (and perhaps even in $F_d$) are $(d+1)$colorable. 


There are two interesting classes of directed planar graphs (where the undirected graph is 3connected). One class consist of planar directed graphs with an acyclic unique sink property: those are acyclic orientation so that every cycle corresponding to a 2 face has a unique sink. A more restricted class correspond to orientations that arise by some linear functional on R^3 for some realization of the graph as a graph of a 3polytope. Those (by a theorem of Klee and Mihalisin) require the additional property that between the unique source and unique sink of the graph there are three vertex disjoint directed paths. 


Resembling the "quasiplanar graphs" that Joe Malkevitch mentioned, you have the class of graphs with crossing number (in the plane) at most k for any $k \geq 0$. For $k = 0$ these are exactly the planar graphs. The crossing number gives an upper bound on the genus, although the bound isn't close to tight in general. By the crossing number inequality, sufficiently large graphs with crossing number at most k are always sparse (with "sufficiently large" depending on k, of course). 


There is a nice generalization of all finite graphs via the notion of a graphlike space, introduced by Thomassen and Vella. A graphlike space is a compact metric space $G$ with a subset $V$ satisfying:
Notice that the definition is purely topological, so it makes sense to define a planar graphlike space as a graphlike space which is homeomorphic to a subset of the sphere. In this context, there is the following deep generalization of Kuratowski's theorem due to Thomassen. Theorem. Let $G$ be a 2connected, compact, and locally connected metric space. Then $G$ is homeomorphic to a subset of the sphere if and only if $G$ does not contain a subspace homeomorphic to $K_{3,3}$ or $K_5$. Here, 2connected means that $G$ is connected and $Gx$ is connected for all $x \in G$. The thumbtack space consists of a disk together with a closed interval glued to the centre of the disk at one endpoint. Notice that the thumbtack space is not planar, but yet does not contain a subspace homeomorphic to $K_{3,3}$ or $K_5$. Thus, 2connectedness is a necessary hypothesis in the above theorem. In addition to generalizing all finite graphs, graphlike spaces also generalize various compactifications of infinite graphs. 


A group having a planar Cayley graph is sometimes called planar. Finite planar groups are well understood. The situation with infinite planar groups and their Cayley graphs is much more complicated; in particular, if the number of ends is infinite. Edit: A flavor of the infinite ended case can be obtained from the following example: Take the truncated cube as a Cayley graph for the group $G$ generated by an element $a$ of order 3 and an involution $b$. If you amalgamate $G$ by itself over a cyclic subgroup generated by $a$, the resulting Cayley graph is planar, but it has infinitely many ends. David Eppstein gave examples of two groups having truncated cube as their Cayley graph. Hence this construction may use either of them or their amalgamated product. The resulting infinite planar graph is a Cayley graph for three distinct groups. 


I am surprised that no one has yet mentioned apex planar graphs. These are graphs $G$ such that there exists a vertex $v \in V(G)$ so that $G  v$ is planar. Apex planar graphs form a minorclosed family. Indeed, more generally, if we start with any minor closed family and 'apex' it, then we get another minorclosed family. Apex vertices are also one of the ingredients in Robertson and Seymour's Graph Minors Structure Theorem, which describes the class of graphs with no $K_n$minor. Probably the most famous open problem along these lines is Jorgensen's Conjecture, which asserts that every 6connected graph with no $K_6$minor is apex planar. 


Alon Amit already has mentioned above the generalization where you ask whether a d dimensional simplicial complex can be embedded continuously to a 2*d*dimensional space. The case of 1 = d gives planar graphs. Jiří Matoušek: Using the BorsukUlam Theorem however notes that you get a different generalization if you ask for an embedding where every simplex of the original complex is embedded linearly. (This is thus not a topological invariant of the simplicial complex.) This too is a true generalization of the class of planar graphs, for every planar graph can be drawn with straight edges. 


A well ordering, $\leq$, on a set $S$ is a WELLQUASIORDERING if and only if every sequence $x_i\in S$ there exists some $i$ and $j$ natural numbers with $i < j$ with $x_i\leq x_j$. (See wikipedia article at bottom) RobertsonSeymour Theorem: The set $S=Graphs/isomorphism$ are wellquasiordered under contraction. The corollary of this theorem is that any property $P$ of graphs which is closed under the relation of contraction (meaning if $P(G_2)$ and $G_1\leq G_2$ then $P(G_1)$) is characterized by a finite set of excluded minors (Which is explained below). An example of such a $P$ is planarity, or linkless embeddability of a graph into R^3. i.e. Every contraction of a planar graph is planar. Suppose $P$ is a property closed under $\leq$. ***If $B\leq G$ and $B$ is not $P(B)$, Then not $P(G)$. The idea is to characterize $P$ by a collection of bad $B$'s. The finiteness of the set of excluded minors comes from the wellquasi ordering and doesn't use the idea of a graph: Assuming we have wellquasiordered set $(S,\leq)$. One can prove that every property $P$ which is closed under the relation is characterized by a Finite set of excluded minors.That is, there exists some $X=\lbrace x_1,\ldots,x_n\rbrace \subset S \ $ such that for all $s\in S$, $$ \mbox{ not } P(s) \iff \exists i, x_i \leq s $$. The existence of a finite set $X$ is implicitly in 12.5 of Diestel (link at bottom, see the corollary of Graph Minor Theorem in Diestel). First convince yourself that there exists a set of $B's$ (not necessarily finite) as in * that characterize property $P$. Then consider the smallest such set of $B$'s and using the property of wellquasi ordering show that is is finite. Note that as in the second wikipedia article, we can say any set of elements $A\subset S$ such that for all $a,b\in A$ we have $a \nleq b$ must be a finite set (provided $\leq$ is a wellquasiordering). Actual work done showing stuff in a topological direction has be done by Eran Nevo http://www.math.cornell.edu/~eranevo/ I suspect that Matroids have a wellquasiordering and that there is work being done toward proving an analogous theorem for them. I have a limit on links: en.wikipedia.org/wiki/Wellquasiordering en.wikipedia.org/wiki/RobertsonSeymour_theorem diestelgraphtheory.com/GrTh.html 

