Discrete Computational Geometry, Vol. 14 (1995), pp. 331-358.
27-38.
James Abello, Ömer Egecioglu, and Krishna Kumar
Visibility Graphs of Staircase Polygons and the Weak Bruhat Order I:
From Visibility Graphs to Maximal Chains
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, it can be shown that every such visibility graph
contains a vertex such that the subgraph induced by the closed neighborhood of
this vertex is isomorphic to the visibility graph of a convex fan.
In this, and a companion paper, we address the characterization and
recognition of visibility graphs of convex fans. We first obtain a complete
characterization and a polynomial time recognition algorithm for visibility graphs of
orthogonal convex fans, also known as staircase polygons. The
proof is based on a direct specialization of a technique used to compute
the visibility graph of an arbitrary simple polygon from a combinatorial
encoding of the underlying configuration of points. The characterization of
visibility graphs of general convex fans, and a polynomial time
recognition algorithm in the case when a hamiltonian cycle is presented
as part of the imput to the problem, follows as a consequence.
Any nondegenerate 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, we define a class of graphs called
persistent graphs and show that the visibility graph of a
staircase polygon is persistent. We then describe an algorithm that recovers a
representative maximal chain in the weak Bruhat order from a given
persistent graph. In the companion paper we show how to reconstruct a
configuration of points and a staircase polygon from the maximal chain
by the algorithm in this paper.
These results are then generalized to obtain a characterization and a
recognition algorithm from the visibility graph of general convex fans.
omer@cs.ucsb.edu