Segment Endpoint Visibility Graphs

Michael Hoffmann¹, and Csaba D. Tóth<sup>2

1</sup> Institute for Theoretical Computer Science, ETH Zürich
² Department of Computer Science, UC Santa Barbara

The segment endpoint visibility graph Vis(S) is defined for a set S of n disjoint closed line segments in the plane. Its vertices are the 2n segment endpoints; two vertices a and b are connected by an edge, if and only if the corresponding line segment ab is either in S (which we call segment edges) or if the open segment ab does not intersect any segment from S ( visibility edges). See the figure below for an example.

  

Figure: A segment endpoint visibility graph; visibility edges are drawn as dotted segments.

The talk focuses on three properties of this graph.

1.

If not all segments in S are collinear, the graph Vis(S) is Hamiltonian. Moreover, there exists a Hamiltonian circuit corresponding to a simple polygon in the plane (Hamiltonian Polygon).

2.

For any set S the graph Vis(S) contains an encompassing tree, which is defined as a planar embedding of a tree with maximal degree three that contains all segment edges.

3.

A path in Vis(S) is called alternating, if every other edge of it is a segment edge. Denote by a(S) the maximum length (=#vertices) of an alternating path in Vis(S), and let $l(n):= \inf_{S,\, \vert S\vert=n} a(S)$. Then for n > 40

$$2\log_2(n+2)-2 \le l(n) < 7.57\,\log_2 n\;.$$