Summary: A simple graph \(G\) with \(p\) vertices is said to be vertex-Euclidean if there exists a bijection \(f: V(G)\rightarrow\{1, 2, \dots, p\}\) such that \(f(v_1) + f(v_2) > f(v_3)\) for each \(C_3\)-subgraph with vertex set \(\{v_1, v_2, v_3\}\), where \(f(v_1) < f(v_2) < f(v_3)\). More generally, the vertex-Euclidean deficiency of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) is vertex-Euclidean. To illustrate the idea behind this new graph labeling problem, we study the vertex-Euclidean deficiency of two new families of graphs called the complete fan graphs and the complete wheel graphs. We also explore some related problems, and pose several research topics for further study.