Edit: As David Eppstein points out (in his answer below) the assumption that the graph is non-planar is redundant. 

Thank you to everyone who answered/commented.

----

I have a problem about geometric embeddings of graphs for which the case I cannot prove is when the (simple, connected) graph is 4-regular, non-planar and has girth at least 5.

I would like to get some intuition for such graphs - e.g. 

*small(est) examples, 

*do such graphs have any interesting special properties?

*I assume there are many when the number of vertices is large, 

*a book or paper that might help.

Apologies if this is too easy for math overflow, I'm not a graph theorist.