Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains (Q1900971)

Given a finite simple polygon, its visibility graph is obtained by connecting those pairs of vertices whose edge is not obstructed by exterior points of other vertices. Characterizing visibility graphs is not yet settled as to minimal complexity. Convex fans may play an important role in settling the question. In this interesting paper the subject is orthogonal complex fans (staircase polygons) whose visibility graphs are proven to be persistent graphs, where persistency is a property of the adjacency matrix of the graph under a suitable ordering of the vertices. Since simple polygons can be associated with maximal chains in the weak Bruhat order of the symmetric group \(S_n\), with \(n\) the number of vertices of the polygon, a polynomial-time algorithm which recovers representative maximal chains from the graph (in a certain class) would effectively answer the characterization question for visibility graphs if they were in that class. The polynomial-time algorithm constructed as a clever concatenation of two subalgorithms of independent interest recovers maximal chains for the class of persistent graphs in polynomial time \(O (n^5)\). The step from persistent graph to visibility graph of a staircase polygon as a logical next step has not been addressed in this paper, but elsewhere.