Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph

In order to find a 2-factor of a graph, there exists a O(n ^1.5) deterministic algorithm 7] and a O(n ³) randomized algorithm 14]. In this paper, we propose novel O(nlog³ nloglogn) algorithms to find a 2-factor, if one exists, of a graph in which all n vertices have degree 4 or less. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes. A 2-factor of such graphs implicitly defines a linear ordering of the mesh primitives in the form of strips. Further, by introducing a few additional primitives, we reduce the number of tetrahedral strips to represent the entire tetrahedral mesh and represent the entire quad surface using a single quad strip.