  Extracting a Construction Tree from potentially noisy point clouds is an
important aspect of Reverse Engineering tasks in Computer Aided Design.
Solutions based on algorithmic geometry impose constraints on usable model
representations (e.g. quadric surfaces only) and noise robustness.
Re-formulating the problem as a combinatorial optimization problem and solving
it with an Evolutionary Algorithm can mitigate some of these constraints at the
cost of increased computational complexity. This paper proposes a graph-based
search space partitioning scheme that is able to accelerate Evolutionary
Construction Tree extraction while exploiting parallelization capabilities of
modern CPUs. The evaluation indicates a speed-up up to a factor of $46.6$
compared to the baseline approach while resulting tree sizes increased by
$25.2\%$ to $88.6\%$.
