Visibility graphs of staircase polygons and the weak Bruhat order, I: From visibility graphs to maximal chains

The recognition problem for visibility graphs of simple polygons is not known to be in NP, nor is it known to be NP-hard. It is, however, known to be in PSPACE. Further, every such visibility graph can be dismantled as a sequence of visibility graphs of convex fans. Any nondegenerated configuration of n points can be associated with a maximal chain in the weak Bruhat order of the symmetric group S _n . The visibility graph of any simple polygon defined on this configuration is completely determined by this maximal chain via a one-to-one correspondence between maximal chains and balanced tableaux of a certain shape. In the case of staircase polygons (special convex fans), we define a class of graphs called persistent graphs and show that the visibility graph of a staircase polygon is persistent. We then describe a polynomial-time algorithm that recovers a representative maximal chain in the weak Bruhat order from a given persistent graph, thus characterizing the class of persistent graphs. The question of recovering a staircase polygon from a given persistent graph, via a maximal chain, is studied in the companion paper [4]. The overall goal of both papers is to offer a characterization of visibility graphs, of convex fans.