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

J. Abello, O. Egecioglu, K. Kumar

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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 languageEnglish (US)
Pages (from-to)331-358
Number of pages28
JournalDiscrete & Computational Geometry
Volume14
Issue number1
DOIs
StatePublished - Dec 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Visibility graphs of staircase polygons and the weak Bruhat order, I: From visibility graphs to maximal chains'. Together they form a unique fingerprint.

Cite this