Network function virtualization (NFV) and Software Defined Networks (SDN) separate and abstract network functions from underlying hardware, creating a flexible virtual networking environment that reduces cost and allows policy-based decisions. One of the biggest challenges in NFV-SDN is to map the required virtual network functions (VNFs) to the underlying hardware in substrate networks in a timely manner. In this paper, we formulate the VNF placement problem via Graph Pattern Matching, with an objective function that can be easily adapted to fit various applications. Previous work only considers off-line VNF placement as it is time consuming to find an appropriate mapping path while considering all software and hardware constraints. To reduce this time, we investigate the feasibility and effectiveness of path-precomputing, where paths are calculated prior to placement. Our approach enables online VNF placement in SDNs, allowing VNF requests to be processed as they arrive. An online placement approach (OPA) is proposed to place VNF requests on substrate networks. To the best of our knowledge, this is the first work in the literature that considers the online chaining VNF placement in SDNs. In addition, we present an application of OPA over cost minimization. Simulation results demonstrate that our online approach provides competitive performance compared with off-line algorithms.