Alternating paths along axis-parallel segments (Q882782)

\(Vis(S)\) denotes the segment endpoint visibility graph of a set \(S\) of pairwise disjoint line segments in the plane. An alternating path for a set \(S\) of pairwise disjoint line segments in the plane is a simple path \(\pi \) in the segment endpoint visibility graph \(Vis(S)\) where segment edges and visibility edges alternate. The author showed that any \(n\) disjoint segments with only two distinct orientations admit an alternating path of length \(\Omega (\sqrt{n})\) and this bound is best possible apart from a constant factor. Some of the results given in the theorems are as follows: For any \(n\)-pairwise disjoint axis-parallel segments in the plane, there is a simple alternating path of length at least \(\sqrt{n/2}\). For any \(n\in \mathbb{N}\), there are \(n\) pairwise disjoint axis-parallel segments in the plane such that the length of any alternating path is at most \(4\sqrt{3n+4}+8\). Every finite protruded set of pairwise disjoint axis-parallel line segments in the plane admits a simple Hamiltonian alternating path, and for every finite set \(S\) of pairwise disjoint axis-parallel segments in the plane there is a \(1\)-\(2\)-alternating path through all segments of \(S\). At the end of the paper also some open questions are stated.