The reference given in [the Wikipedia article on linkless embedding][1] for the $4n-10$ bound on the number of edges in a linkless embeddable graph is Mader, W. (1968), "Homomorphiesätze für Graphen", Mathematische Annalen 178 (2): 154–168, doi:10.1007/BF01350657. Apparently Mader proves this bound more generally for $K_6$-minor-free graphs. As the Wikipedia article also states, the example of apex graphs shows that this is tight.

As for the Colin de Verdière invariant: it is known to be at least the [size of the largest clique minor][2] minus one – e.g. see http://homepages.cwi.nl/~lex/files/cdvsurvey_new2.pdf – and combining this with the Kostochka/Thomason results cited by Tony Huynh shows that the edge density can grow at most slightly superlinearly as a function of the CdV invariant.


  [1]: https://en.wikipedia.org/wiki/Linkless_embedding
  [2]: https://en.wikipedia.org/wiki/Hadwiger_number