We consider shortest path queries in a polygonal domain P having n vertices and h holes. A skeleton graph is a subgraph of a Voronoi diagram of P. Our novel algorithm utilizes a reduced skeleton graph of P to compute a tessellation of P. It builds a data structure of size O(n 2) in O(n 2logn) time to support distance queries for any pair of query points in P in O(hlogn) time.