Service discovery is an integral part of the ad hoc networking to achieve stand-alone and self-configurable communication networks. In this paper, we discuss possible service discovery architectures along with the required network support for their implementation, and we propose a distributed service discovery architecture which relies on a virtual backbone for locating and registering available services within a dynamic network topology. Our proposal consists of two independent components: (i) formation of a virtual backbone and (ii) distribution of service registrations, requests, and replies. The first component creates a mesh structure from a subset of a given network graph that includes the nodes acting as service brokers and a subset of paths (which we refer as virtual links) connecting them. Service broker nodes (SBNs) constitute a dominating set, i.e. all the nodes in the network are either in this set or only one-hop away from at least one member of the set. The second component establishes subtrees rooted at service requesting nodes and registering servers for efficient dissemination of the service discovery probing messages. Extensive simulation results are provided for comparison of performance measures. i.e. latency, success rate, and control message overhead, when different architectures and network support mechanisms are utilized in service discovery.