On the existence of paths and cycles
Hoffmann, Michael · Repository for Publications and Research Data (ETH Zurich) · 2005
This thesis investigates questions related to the existence of certain paths and cycles in graphs.Its major part is centered around the fol¬ lowing question: Given a set of n line segments in the plane, can one connect all segment endpoints by a closed path that does not cross itself nor any of the segments?In other words, under which conditions can one find a simple polygon P whose vertices are the segment endpoints and such that P does not cross any segment?(The segmentsmay appear as edges of P.) Such polygons are known as Hamiltonian polygons and the moti¬ vation to study them is twofold: • Traversais of line segments are a natural generalization of the Euclidean Traveling Salesman Problem (Etsp) for points in the plane.• Statementsabout the existence of paths or cycles through line seg¬ ments are structural results about the so-called visibility graph of the segments.Visibility graphs are important geometric struc¬