Polyhedral combinatorics has been a topic of interest in modern day’s computational geometry.
The founding of Steinitz’s Theorem in 1922 revealed consequential relations between graph
theory and polyhedral combinatorics. It allows us to better investigate on the topology of
convex polyhedrons. In this paper, we proposed an algorithm that generates a unique sequence
of points, using the vertices of a triangulated polyhedron, pre-determined by the selection of
the starting 3 vertices in the sequence. Following that, we discover an interesting relation
between the sequence and the volume of the polyhedron itself, in which we presented in the
form of a sufficient condition. To further investigate which polyhedrons generate sequences
that satisfy the sufficient condition, we study the problem in the context of graph theory, that
is, the explorer walk (corresponding to the sequence of vertices) in maximal planar graphs
(skeletons of triangulated convex polyhedrons). With that, we uncovered a family of maximal
planar graphs, called the explorer graphs, which exhibits volumetric properties in the
polyhedrons constructed from them, in regard to the explorer walk. In this paper, we also
introduce generalized methods of constructing explorer graphs of higher order from explorer
graphs of lower order, demonstrating the prevalence of explorer graphs. As the edges of a
maximal planar graph is of great importance in tracing an explorer walk, we investigate on the
line graph of maximal planar graphs, and re-establish a better definition of explorer graphs.
Lastly, our paper covers the edge contraction of explorer graphs, which allows us to solve the
volume of polyhedrons constructed from non-explorer graphs. For this, we presented a possible
bound for the minimum number of edge contractions a non-explorer graph requires from an
explorer graph. This will generalize the proposed method of finding volumes to any
triangulated convex polyhedron.