Abstract
This paper is concerned with the fast computation of a relationon the edge set of
connected graphs that plays a decisive role in the recognition of approximate Cartesian
products, the weak reconstruction of Cartesian products, and the recognition of Cartesian
graph bundles with a triangle free basis.
A special case ofis the relation, whose convex closure yields the product relation
that induces the prime factor decomposition of connected graphs with respect to the
Cartesian product. For the construction of so-called Partial Star Products are of particular
interest. Several special data structures are used that allow to compute Partial Star Products
in constant time. These computations are tuned to the recognition of approximate graph
products, but also lead to a linear time algorithm for the computation of for graphs with
maximum bounded degree.
Furthermore, we define quasi Cartesian products as graphs with non-trivial. We
provide several examples, and show that quasi Cartesian products can be recognized in
linear time for graphs with bounded maximum degree. Finally, we note that quasi products
can be recognized in sublinear time with a parallelized algorithm.
