Interesting families of sparse graphs? - MathOverflow

Interesting families of sparse graphs?

2009-10-23T14:30:13Z

I'm interested in graph families which are sparse, and by sparse I mean the number of edges is linear in the number of vertices. |E| = O(|V|). Besides non-trivial minor-closed families of graphs (these turn out to be sparse), I don't know any other families. Can anyone suggest any interesting graph families (which are not minor-closed) which are sparse?

Please don't suggest the trivial family ("the family of sparse graphs").

EDIT: Thanks to the first few people who replied, I realized that bounded degree graphs (max degree < k) also form an interesting and large class of sparse graphs. So perhaps I'll refine my question to exclude those too. Any interesting sparse graph families where the max degree isn't bounded? For example the family of star graphs is sparse and not bounded degree. (But they're minor-closed.)

Answer by Alon Amit for Interesting families of sparse graphs?

2009-10-23T15:12:29Z

Well, for any d, the family of d-regular graphs is sparse in your sense and not minor closed. I don't suppose this is what you're after, so perhaps you can refine the question?

EDIT: naturally, there are variations on this theme - graphs of bounded degree, graphs of bounded degree with additional degree restrictions, graphs which cover (in the topological sense) a fixed base graph, ...

Answer by JSE for Interesting families of sparse graphs?

2009-10-23T15:26:29Z

Cayley graphs of groups generated by 2 (or any fixed number) of elements?

Answer by Sonia Balagopalan for Interesting families of sparse graphs?

2009-10-23T15:27:17Z

Expander graphs are regular, hence sparse, and have a lot of interesting properties and applications. Elementary Number Theory, Group Theory, and Ramanujan Graphs by Davidoff, Sarnak, and Valette is an excellent introduction. A Google search for expander graphs also turns up a lot of material.

Answer by David Eppstein for Interesting families of sparse graphs?

2009-10-23T17:01:00Z

Minimally rigid graphs in d dimensions. For d=2 these are the Laman graphs but I don't think any kind of clean combinatorial description of these graphs is known for higher dimensions.

Answer by Ilya Nikokoshev for Interesting families of sparse graphs?

2009-10-23T21:02:19Z

You need examples, right? Internet, local networks, social connections :)

Answer by Boris Bukh for Interesting families of sparse graphs?

2009-10-23T21:37:40Z

1) Graphs of degree at most d. There are a myriad results known about them. Among them there are regular graphs (graphs in which every vertex is of degree exactly d).

2) Graphs of bounded degeneracy. These are the graphs in which every subgraph has a vertex of degree at most d. For example, stars have unbounded degree, but degeneracy 1. These share some common properties with graphs of bounded degree. For example, there are several results in Ramsey theory that have been extended from graphs of bounded degree to graphs of bounded degeneracy.

3) Random graphs of edge density c/n for constant c. Strictly speaking these are not a 'family of graphs', but since for properties of interest a random graph usually either satisfies it with high probability or fails it with high probability, it is fair to add them. There are also various other models of random graph that yield sparse graphs.

4) On a lower level, there are particular subfamilies of the above, such as stars, grids, etc.

Answer by Harrison Brown for Interesting families of sparse graphs?

2009-10-24T02:05:39Z

Although they're not as commonly studied, you can define expander families where the max degree isn't bounded.

You can also approach expanders from a spectral perspective (expansion properties have to do with how small the second-largest eigenvalue is), and if you do that, then you can also consider graphs with small third-largest eigenvalue, fourth-largest eigenvalue, etc. These aren't nearly as interesting or important as expanders, but they occasionally have their uses.

Answer by daysweetener for Interesting families of sparse graphs?

2009-10-31T23:15:05Z

A topological graph which is k-quasi-planar is a topological graph which does not contain k pairwise crossing edges. It is conjectured that for a fixed k, such a graph is sparse. This conjecture is known to hold if k=2 (in that case the graph is planar) and if k=3,4. The conjecture is open as far as I know for larger k.

Answer by Jon Awbrey for Interesting families of sparse graphs?

2010-05-26T19:08:24Z

One family of graphs that bears unlimited degrees of computational fruit has been dubbed (by me) painted and rooted cacti (PARCs). Painted just means that you can associate any subset of a finite palette $\mathcal{P} = \lbrace p_1, \ldots, p_k \rbrace $ of colors $p_j$ with each node of the underlying rooted cactus.

PARCs can be interpreted as propositional calculus formulas in a couple of ways that are logically dual to each other, extending the graphical syntax for propositional logic that C.S. Peirce called his Alpha graphs, with their entitative and existential readings.

I'll dig up some links …

I'd completely forgotten — here's a sparse exposition of cactus calculus (in the so-called existential interpretation) that I'd already posted on another question.

Answer by vb le for Interesting families of sparse graphs?

2013-01-17T00:23:37Z

Let me recommend the book J. Nešetřil and P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, Springer 2012. It is the first systematic study of sparse graphs and related topics.