VISIBILITY GRAPHS OF STAIRCASE POLYGONS AND THE WEAK BRUHAT ORDER .1.FROM VISIBILITY GRAPHS TO MAXIMAL-CHAINS

The recognition problem for visibility graphs of simple polygons is no t known to be in NP, nor is it known to be NP-hard. It is, however, kn own to be in PSPACE. Further, every such visibility graph can be disma ntled as a sequence of visibility graphs of convex fans. Any nondegene rate configuration of n points can be associated with a maximal chain in the weak Bruhat order of the symmetric group S-n. The visibility gr aph of arty simple polygon defined on this configuration is completely determined by this maximal chain via a one-to-one correspondence betw een maximal chains and balanced tableaux of a certain shape. In the ca se of staircase polygons (special convex fans), we define a class of g raphs called persistent graphs and show that the visibility graph of a staircase polygon is persistent. We then describe a polynomial-time a lgorithm that recovers a representative maximal chain in the weak Bruh at order from a given persistent graph, thus characterizing the class of persistent graphs. The question of recovering a staircase polygon f rom a given persistent graph, via a maximal chain, is studied in the c ompanion paper [4]. The overall goal of both papers is to offer a char acterization of visibility graphs of convex fans.