Generalizations of planar graphs that include hypercubes with large side length in $R^d$

Question

A lot of people have asked about generalizations of planar graphs on other forums. Some topics include:

https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs https://math.stackexchange.com/questions/22714/higher-dimensional-analog-to-planar-graphs

Many have talked about minor-closed family generalizations of planar graphs, but they cannot possibly include even 3D n by n by n grids. If they did, then n by n by n grids would have to have balanced separators of size $n^{3/2}$, but in reality all of their balanced separators have size at least $n^2$. Qiaochu's definition focuses more on the direction that I am interested in. Ideally, I would like to look at graphs that are 1-skeleta of $(k-1)$-dimensional cell complexes that can be embedded in $\mathbb{R}^k$ injectively (which may be the same thing that Qiaochu is looking for). These are not minor closed for $k\ge 3$, but might be face-contraction closed.

Have these graphs been studied algorithmically? For example, can one generalize the planar separator theorem to these graphs? Or is there something particularly nasty about this definition that I am overlooking that prevents these objects from being algorithmically interesting?

Answer 1

You may want to look at nowhere dense graphs. http://www.sciencedirect.com/science/article/pii/S0195669811000151

One of the reasons why minor-closedness is natural is the following. We typically want to work with families of graphs rather than specific graphs. And we want to solve problems with arbitrary weights/capacities on edges/nodes. Suppose we want to solve the shortest path problem in a family of graphs. Then, if we allow for zero length and infinite lengths then basically we are allowing minor operations on the family. In some settings it makes sense to work with unweighted graphs where positive results can be obtained for larger families of graphs that are not necessarily minor-closed.