Discrete Computational Geometry, (to appear).
James Abello, Ömer Egecioglu, and Krishna Kumar
Visibility Graphs of Staircase Polygons and the Weak Bruhat Order II:
From Maximal Chains to Polygons
Abstract.
This is the second of two papers that address the characterization and
recognition of visibility graphs of convex fans. We first obtain a
characterization and polynomial recognition algorithm for
orthogonal convex fans, also called staircase polygons.
In the first paper, it is shown that these visibility graphs belong to a class
of graphs known as persistent graphs, and that they can be derived from
a combinatorial encoding of the underlying configuration of points by
maximal chains in the weak Bruhat order of the symmetric group $S_n$. That
paper also describes an algorithm that constructs a maximal chain
corresponding to a given persistent graph.
In this paper we show that the maximal chains that are constructed by the
algorithm in the first paper are realizable by non-degenerate
configurations of points in the plane. The proof is
constructive and implies a polynomial time algorithm for the
reconstruction problem for these visibility graphs. These results
allow us to obtain complete characterizations and efficient recognition
algorithms for this class of visibility graphs. We obtain a
characterization for visibility graphs of general convex fans as a by-product.
This gives us a polynomial time recognition algorithm for the
recognition of visibility graphs of general convex fans when a hamiltonian
cycle is specified as part of the input.
The general 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.
omer@cs.ucsb.edu