$\newcommand\P{\mathbb P}$Some time ago someone posted an answer to this question and promptly deleted it. I thought that the answer was worth writing. I waited a bit to see if a revised version of this answer would be posted but this never happened. I am not sure why it was deleted as I couldn't find anything wrong with the answer. I will repost the answer with credits to that person (whom I unfortunately do not know):
The paper
On Degrees and Genera of Curves on Smooth Quartic Surfaces in $\P^3$, Mori, Nagoya Math. Journal, Vol 96, p.127-132, 1984.
proves that the curves in the graph associated with the empty "don't know yet" circles do exist. The curves that Mori finds lie on a smooth quartic surface and the condition for this to occur is given in his Theorem 1:
Let $k$ be an algebraically closed field of characteristic $0$ and
$d>0$ and $g\ge 0$ be integers. Then there is a non-singular curve $C$
of degree $d$ and genus $g$ on a non-singular quartic surface $X$ in
$\P^3$ iff
- $g=d^2/8 +1$ or
- $g<d/8$ and $(d,g)\ne (5,3)$
Mori's paper also cite a work of Gruson and Peskin, written in French, where a similar thing was proven except that $X$ is considered to be a singular quartic surface instead. Still it seems that not everything under the curve $g=\frac 14 d^2-d+1$ is known.