## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 331-358 |

Number of pages | 28 |

Journal | Discrete & Computational Geometry |

Volume | 14 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1995 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics