Question

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.

Answer 1

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

Answer 2

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 (Koebe-Thurston-Andreev), they have at most a linear number of edges in any dimension, and more importantly from the point of view of divide-and-conquer algorithms they have separator theorems in any dimension (Shang-Hua Teng and others).

Answer 3

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

Answer 4

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

Answer 5

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:

Quasi-planar graphs have a linear number of edges

http://www.springerlink.com/content/v276423723348224/

-Joe Malkevitch

Answer 6

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, minor-closed families (which avoid some graph), graphs of simple d-polytopes 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 d-speheres 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 d-polytopes have a seperation theorem.)

Answer 7

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.

Answer 8

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 3-space. 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.

Answer 9

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.

Answer 10

Graphs which are stress-free 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 3n-6.) 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 3-rigid, and this result is based on Dehn-Alexandrov's theorem asserting that (embedded) graphs of simplicial 3-polytopes are infinitesimally rigid.

Answer 11

There are two interesting classes of directed planar graphs (where the undirected graph is 3-connected). 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 3-polytope. 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.

Answer 12

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

Answer 13

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 (k-3) 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 (d-1)-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.

Answer 14

There is a nice generalization of all finite graphs via the notion of a graph-like space, introduced by Thomassen and Vella. A graph-like space is a compact metric space $G$ with a subset $V$ satisfying:

1. $V$ is totally disconnected,

2. $G-V$ consists of disjoint open sets of $G$,

3. each component of $G-V$ is homeomorphic to $\mathbb{R}$, and has exactly two limit points in $V$.

Notice that the definition is purely topological, so it makes sense to define a planar graph-like space as a graph-like 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 2-connected, 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, 2-connected means that $G$ is connected and $G-x$ 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, 2-connectedness is a necessary hypothesis in the above theorem.

In addition to generalizing all finite graphs, graph-like spaces also generalize various compactifications of infinite graphs.

Answer 15

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.

Answer 16

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.

Answer 17

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 T-f+e is a tree.)

There is even a Kuratowski-type theorem for characterizing circle graphs, which actually implies the Kuratowski theorem for planar graphs. http://dx.doi.org/10.1002/jgt.v61:1

Answer 18

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 minor-closed family. Indeed, more generally, if we start with any minor closed family and 'apex' it, then we get another minor-closed 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 6-connected graph with no $K_6$-minor is apex planar.

Answer 19

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 Borsuk-Ulam 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.

Answer 20

A well ordering, $\leq$, on a set $S$ is a WELL-QUASI-ORDERING 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)

Robertson-Seymour Theorem: The set $S=Graphs/isomorphism$ are well-quasi-ordered 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 well-quasi ordering and doesn't use the idea of a graph: Assuming we have well-quasi-ordered 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 well-quasi 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 well-quasi-ordering).

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 well-quasi-ordering and that there is work being done toward proving an analogous theorem for them.

I have a limit on links:

en.wikipedia.org/wiki/Well-quasi-ordering

en.wikipedia.org/wiki/Robertson-Seymour_theorem

diestel-graph-theory.com/GrTh.html