36
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Muktiple answers/posts are welcomed. I hope we can have a useful source. $\endgroup$
    – Gil Kalai
    Commented Dec 3, 2009 at 17:51
  • $\begingroup$ More answers, remarks, links are most welcome. In particular: links to connections between planar graphs and commutative algebra (and other algebra), some info on the simlicial complex of (edges of) planar graphs on n vertices, some interesting extensions of planar graphs related to the 4CT. $\endgroup$
    – Gil Kalai
    Commented Dec 19, 2009 at 14:58

21 Answers 21

Reset to default
17
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Dear Alon, this is a very important and interesting generalization. $\endgroup$
    – Gil Kalai
    Commented Dec 3, 2009 at 10:05
  • 2
    $\begingroup$ Already in the $m=2$ case this is a non-trivial question. There are some positive results -- such complexes $M$ embed if $H^2(M;\mathbb Z)$ is cyclic. M. Kranjc, "Embedding a 2-complex K in R^4 when H^2(K) is a cyclic group," Pac. J. Math. 150 (1991), 329-339. There's also some known obstructions to embedding: A. Shapriro, "Obstructions to the imbedding of a complex in Euclidean space, I. The first obstruction," Ann. of Math., 66 No. 2 (1957), 256--269. $\endgroup$
    – Ryan Budney
    Commented Dec 3, 2009 at 15:35
  • $\begingroup$ I think that embeddability of 2 dimensional spaces into R^4 is the most difficult case. $\endgroup$
    – Gil Kalai
    Commented Dec 3, 2009 at 19:20
  • $\begingroup$ (This is because of the wonderful Pandora box oppened by Mike Freedman :) ) $\endgroup$
    – Gil Kalai
    Commented Dec 4, 2009 at 10:50
  • $\begingroup$ If you can't construct tame topological embeddings (that aren't smooth) then you stick to smooth embeddings and your life is easier. :) $\endgroup$
    – Ryan Budney
    Commented Dec 4, 2009 at 16:20
15
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Dear Konrad, this is indeed an important generalization of planar graphs. (I am not so sure lambda<=3 gives planarity rather than the very related "not having a K_5-minor".) $\endgroup$
    – Gil Kalai
    Commented Dec 7, 2009 at 16:11
  • $\begingroup$ Dear Gil, Indeed! I'll correct my answer. $\endgroup$
    – Konrad Swanepoel
    Commented Dec 8, 2009 at 15:58
  • $\begingroup$ Just to restate: If $p$ is an integer graph parameter that is minor-monotone (i.e. $p(G) \le p(H)$ whenever $G$ is a minor of $H$) then by Robertson-Seymour for every $k$ the set of graphs $G$ with $p(G) \le k$ is characterized by a finite list of forbidden minors. If $p$ arises "naturally" in some way and it happens that for some $k$ the list of forbidden minors is exactly $K_5$ and $K_{3,3}$, then different values of $k$ provide an infinite family of "natural" generalizations (or specializations) of the class of planar graphs. The two parameters mentioned arguably qualify. $\endgroup$
    – Tracy Hall
    Commented Sep 4, 2010 at 20:21
  • $\begingroup$ The link to sciencedirect.com is broken, but the article can be found at doi:10.1006/jctb.1995.1056, or at the CWI Institutional Repository (Zbl 0839.05034). $\endgroup$
    – The Amplitwist
    Commented May 18, 2023 at 7:00
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ One way that planar graphs are exceptional among minor-closed families is that a minor-closed family includes all planar graphs iff its graphs do not have bounded treewidth. Relatedly, a minor-closed family includes all apex graphs (planar + 1 vertex) iff its graphs do not have bounded local treewidth. $\endgroup$
    – David Eppstein
    Commented Dec 3, 2009 at 23:59
  • $\begingroup$ @David: Your first statement is what I was referring to; I just don't have any idea why this should be the case! $\endgroup$
    – Harrison Brown
    Commented Dec 4, 2009 at 0:48
  • 2
    $\begingroup$ one way of thinking about the relation between including all planar graphs and not having bounded treewidth is this: unbounded treewidth means that the graph family contains large grids (or walls). A grid (or wall) can be converted into an arbitrary planar graph by deletion/contraction operations. So a family that excludes even one planar graph can't have a large grid, and therefore must have bounded treewidth. $\endgroup$
    – Suresh Venkat
    Commented Feb 23, 2010 at 4:26
9
$\begingroup$

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

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Maybe "hypergraph" = "simplicial complex," here? I have to confess, I've spent a lot of time trying to figure out exactly what the deal is with graphs in R^4... $\endgroup$
    – Harrison Brown
    Commented Dec 3, 2009 at 20:13
  • $\begingroup$ One generalization that Kristal point out to is graphs that can be embedded in a given surface. This is perhaps the most studied generalization of planar graphs. Going to higher dimensional objects was suggested by Alon (embeddability of k spaces into R^2k.) Kristal's suggestion to replace the ambient space by other spaces is certainly interesting. If I remember correctly embeddability of k manifolds in Euleriam 2k-manifolds (2k-manifolds with Euler characteristic 2) is equivalent to embeddability in R^{2k}. (OK, maybe the condition is vanishing middle homology and not being Eulerian.) $\endgroup$
    – Gil Kalai
    Commented Dec 4, 2009 at 9:27
7
$\begingroup$

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

https://doi.org/10.1007/BF01196127

-Joe Malkevitch

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Joe, This refer to an important extension of planar graphs: Graphs that can be drawn in the plane by Jordan curves so that there are no r edges that every pair cross. For r=2 these are planar graphs and for r=3 these are the quasi-planar graphs in the linked paper. It is expected but not knwon that for larger r there is a linear bound on the number of edges. $\endgroup$
    – Gil Kalai
    Commented Dec 4, 2009 at 10:20
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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. https://doi.org/10.1002/jgt.v61:1

Improve this answer
$\endgroup$
0
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's a very nice idea! $\endgroup$
    – Gil Kalai
    Commented Dec 4, 2009 at 9:20
  • $\begingroup$ Since the class of matroids representable over any fixed F is also closed under duality, I'm not sure this is a meaningful generalization. For example, the class of matroids representable over the reals is somehow not very planar (or even graph-like). $\endgroup$
    – Tony Huynh
    Commented Feb 22, 2010 at 23:05
  • $\begingroup$ @Tony: Actually, that's one of the reasons why I think this is interesting! The idea being that the class of planar graphs has some "nicer" algebraic properties than the class of all graphs... $\endgroup$
    – Harrison Brown
    Commented Mar 11, 2010 at 8:13
  • $\begingroup$ Combining this with your other idea, one can consider minor-closed families of matroids. $\endgroup$
    – Timothy Chow
    Commented Mar 8, 2011 at 17:06
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ That's very interesting! I heard about real trees (R-trees) which play important role but not about these spaces. $\endgroup$
    – Gil Kalai
    Commented Feb 23, 2010 at 21:08
  • $\begingroup$ I myself did not know about real trees, but after passing through a few children websites I found them. en.wikipedia.org/wiki/Real_tree Much thanks. The nice thing about graph-like spaces is that they really are 'graph-like'. For example, they satisfy a form of Menger's theorem. Also, Maclane's theorem and Whitney's theorem hold for the planar ones. $\endgroup$
    – Tony Huynh
    Commented Feb 24, 2010 at 16:13
4
$\begingroup$

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 (Wayback Machine), which asserts that every 6-connected graph with no $K_6$-minor is apex planar.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Tony, thanks for the answer. Let me mention that the class E_d of graphs of elementary 4-polytopes and their subgraphs contains the class of apex graphs. $\endgroup$
    – Gil Kalai
    Commented Mar 8, 2011 at 5:56
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Tomaž, that's very tantalising! Who understands it? Can you provide links or references? $\endgroup$
    – LSpice
    Commented Mar 11, 2010 at 2:10
  • $\begingroup$ Loren, a good starting point is chapter "The genus of a group", by Tom Tucker that appeared in "Topics in Topological Graph Theory",(L.W. Beineke, R.J. Wilson, eds.), Encyclopedia of Mathematics and Its Applications 128, Cambridge Univ. Press, 2009. $\endgroup$
    – Tomaž Pisanski
    Commented Mar 11, 2010 at 6:15
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ st-planar graphs (directed acyclic plane graphs in which there is only one source and one sink, both on the outer face) are another class of directed planar graphs, important in graph drawing. $\endgroup$
    – David Eppstein
    Commented Dec 7, 2009 at 7:16
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

Wagner-Fáry-Stein theorem states that each (finite simple) planar graph admits a straight-line crossing-free plane drawing. On the other hand, each graph (of at most $\frak c$ vertices) admits a straight-line crossing-free three-dimensional space drawing (any placement of vertices with no four at one plane generates such a drawing). Recently we investigate the minimum number of planes that together cover a straight-line drawing of a graph, which turned out to be independent on dimension of the space in which the graph is drawn, provided this dimension is at least three. Also, since any straight-line and circular-arc drawing can be transformed into a circular-arc drawing by an inversion map, we investigate the minimum number of spheres covering circular arc graph drawings.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This was already mentioned by Harrison (see above). There are a couple of typos. In the first sentence, 'well-ordering' should be replaced by 'quasi-ordering.' With quasi-orderings it is unnecessary to mod out by isomorphism classes. You should also consider edge and vertex deletions when defining minors. For matroid minors, Geelen, Gerards and Whittle recently proved that binary matroids are well-quasi-ordered under taking minors. homepages.cwi.nl/~bgerards They hope to extend this to all finite fields soon. $\endgroup$
    – Tony Huynh
    Commented Feb 23, 2010 at 15:55
  • $\begingroup$ Rad. Thanks for the corrections. Nice to hear about the Matroids. Sorry about not reading the post above above. :-) $\endgroup$
    – Taylor Dupuy
    Commented Feb 23, 2010 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .