Return to Answer

For your first question, Sachs proved that every linklessly embeddable graph on $n$ vertices has at most $4n-10$ edges (this is not true, see comments).

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.

For your first question, Mader proved that all $K_6$-minor-free graphs (which includes all linklessly embeddable graphs) on $n$ vertices have at most $4n-10$ edges (thanks to David Eppstein for the reference).

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.

For your first question, Sachs proved that every linklessly embeddable graph on $n$ vertices has at most $4n-10$ edges.

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.

For your first question, Sachs proved that every linklessly embeddable graph on $n$ vertices has at most $4n-10$ edges (this is not true, see comments).

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.

Since the property of being linklessly embeddable is a minor-closed property, one can apply the graph minors theory of Robertson and Seymour. From the Graph Minors Structure Theorem, graphs in a fixed minor-closed family have a linear number of edges. That is, there is an absolute constant $C$, such that every linklessly embeddable graph on $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges.

Update. In this paper of Sachs, it is proved that every linklessly embeddable graph on $n$ vertices has at most $4n-10$ edges.

The answer to your second question is (most likely) no for 2-manifolds. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem. That is, for a general graph $H$, the genus of graphs without an $H$-minor is not bounded.

For your first question, Sachs proved that every linklessly embeddable graph on $n$ vertices has at most $4n-10$ edges.

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.