9
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ That depends a lot on what you mean by "interesting." Are you a combinatorialist? A computer scientist? A quiver representation theorist? $\endgroup$
    – Qiaochu Yuan
    Commented Oct 23, 2009 at 14:32
  • $\begingroup$ Computer scientist. I'm thinking about graph algorithms for sparse graph families. Hope that helps. $\endgroup$
    – Rune
    Commented Oct 23, 2009 at 15:11

10 Answers 10

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ That was helpful, thanks! I guess my question is a bit vague, but all you said was helpful. $\endgroup$
    – Rune
    Commented Oct 23, 2009 at 15:38
5
$\begingroup$

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.

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

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.

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

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

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

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

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

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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