Springe direkt zu Inhalt

Philipp Walter:

Experimental Evaluation of Algorithms for Long Plane Trees


Longest planar spanning trees are thought to be an NP-hard task. One approach to such problems is to relax the solution’s criteria. This can be achieved by identifying solutions that are not necessarily the longest spanning tree but are planar. This paper investigates the lower bound of the approximation factor of algorithms producing planar spanning trees. We analyze the algorithm proposed in Cabello et al. (2021). The algorithm finds AB trees that improve star graphs. The star is a simple graph proposed by Alon et al. (1993), where one point is connected to every other point. The AB tree algorithm attempts to improve the star by adding zig-zag edges, which increases the total length. To analyze the approximation factors, we implement four algorithms: the aforementioned AB tree algorithm, a brute force algorithm for the longest planar spanning tree, a longest spanning tree algorithm, and a specialized algorithm for convex point sets. A genetic algorithm was used to find point sets with low approximation factors programmatically. The brute force algorithm implementation performed poorly and was only utilized for point sets of no more than 10 points. We analyzed point sets with approximation factors of less than 0.9. The genetic algorithm’s output has an approximation factor of 0.9 as well. The sets with low approximation factors are very elongated point sets, particularly ellipsoid forms. In this work, the lowest approximation factor determined is 0.877. Our analysis finds a more overly stretched graph results in an even lower approximation factor.

Bachelor of Science (B.Sc.)