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

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 inPSPACE. Further, every such visibility graph can be dismantled as a sequence of visibility graphs of convex fans. Any nondegenerated configuration ofn points can be associated with amaximal chain in the weak Bruhat order of the symmetric groupS _n . The visibility graph ofany simple polygon defined on this configuration is completely determined by this maximal chain via a one-to-one correspondence between maximal chains andbalanced tableaux of a certain shape. In the case of staircase polygons (special convex fans), we define a class of graphs calledpersistent 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. The research of J. Abello was supported by NSF Grants Nos. DCR 8603722 and DCR 8896281. This research was done while K. Kumar was at the Department of Computer Science, Texas A & M University.     

Obstacle Numbers of Graphs

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph.     

On the modality of convex polygons

Under two definitions of random convex polygons, the expected modality of a random convex polygon grows without bound as the number of vertices grows. This refutes a conjecture of Aggarwal and Melville.     

On the X-Y convex hull of a set of X-Y polygons

We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.     

Tomography models of random convex polygons

Combinatorial integral geometry possesses some results that can be interpreted as belonging to the field of Geometric Tomography. The main purpose of the present paper is to present a case of parallel X-ray approach to tomography of random convex polygons. However, the Introduction reviews briefly some earlier results by the author that refer to reconstruction of (non-random) convex domains by means of a point X-ray. The main tool in treating the parallel X-rays is disintegrated Pleijel identity, or rather, its averaged version, whose derivation is represented in complete detail. The paper singles out a class of random polygons called tomography models, that offer essential advantages for the analysis. The definition of a tomography model is given in terms of stochastic independence. Fortunately, random translation-invariant Poisson processes of lines in IR ² suggest a class of examples. We recall that each such line process is determined by its rose of directions ρ(?). For rather general ρ(?), the number weighted typical polygon in the polygonal partition of the plane generated by the corresponding Poisson line process happens to be a tomography model. For general tomography models, a differential equation is derived for the Laplace transform for parallel X-rays, that rises several interesting computational problems.     

On polygons circumscribing a closed convex curve

Length and area formulas for closed polygonal curves are derived, as functions of the vertex angles and the distances to the lines containing the sides. Applications of the formulas are made to the class of polygons which circumscribe a given convex curve and have a prescribed sequence of vertex angles. Geometric conditions are given for polygons in the class which have extremal perimeter or area.     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

Universal Coefficient Theorems and a Paper of DINH THE LUC

The consequences of an ergodic assumption for mosaic processes of random convex polygons are explored in detail. Under certain regularity conditions on the “smallness” and “largeness” of polygons it is shown that the geometric characteristics of the so-called “typical” polygons do in fact exist. New formulae concerning these characteristics are given. The polygon process formed by a Poisson line process is considered as an example of the general theory and, as a result, certain properties of this example which were previously given heuristically, are proved. Edge effects are treated rigorously.     

Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

On the number of disjoint convex quadrilaterals for a planar point set

For a given planar point set P, consider a partition of P into disjoint convex polygons. In this paper, we estimate the maximum number of convex quadrilaterals in all partitions.     

Decompositions,Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets.     

Proper interval graphs and the guard problem

This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with 2 vertices have hamiltonian paths, those with 3 vertices have hamiltonian cycles, and those with 4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.     

Geometric Containment Orders: A Survey

A partially ordered set (X, ) is a geometric containment order of a particular type if there is a mapping from X into similarly shaped objects in a finite-dimensional Euclidean space that preserves by proper inclusion. This survey describes most of what is presently known about geometric containment orders. Highlighted shapes include angular regions, convex polygons and circles in the plane, and spheres of all dimensions. Containment orders are also related to incidence orders for vertices, edges and faces of graphs, hypergraphs, planar graphs and convex polytopes. Three measures of poset complexity are featured: order dimension, crossing number, and degrees of freedom.     

Convex lattice polygons with all lattice points visible

Two lattice points are visible to one another if there exist no other lattice points on the line segment connecting them. In this paper we study convex lattice polygons that contain a lattice point such that all other lattice points in the polygon are visible from it. We completely classify such polygons, show that there are finitely many of lattice width greater than 2, and computationally enumerate them. As an application of this classification, we prove new obstructions to graphs arising as skeleta of tropical plane curves.     

Distance-regularised graphs are distance-regular or distance-biregular

One problem with the theory of distance-regular graphs is that it does not apply directly to the graphs of generalised polygons. In this paper we overcome this difficulty by introducing the class of distance-regularised graphs, a natural common generalisation. These graphs are shown to either be distance-regular or fall into a family of bipartite graphs called distance-biregular. This family includes the generalised polygons and other interesting graphs. Despite this increased generality we are also able to extend much of the basic theory of distance-regular graphs to our wider class of graphs.     

The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.     

Convexification of polygons by flips and by flipturns

Simple polygons can be made convex by a finite number of flips, or of flipturns. These results are extended to very general polygons.     

An isoperimetric inequality for convex polygons and convex sets with the same symmetrals

Suppose that two distinct plane convex bodies have the same Steiner symmetrals about a finite number n of given lines. Then we obtain an upper bound for the measure of their symmetric difference. The bound is attained if, and only if, the directions of the lines are equally spaced and the bodies are two regular concentric polygons, with n sides, each obtained from the other by rotation through an angle /n. This result follows from a new isoperimetric inequality for convex polygons.     

Integration of combinatorial decompositions in the presence of collinearities

Many results in Combinatorial Integral Geometry are derived by integration of the combinatorial decompositions associated with finite point sets {P _i } given in the plane ?². However, most previous cases of integration of the decompositions in question were carried out for the point sets {P _i } containing no triads of collinear points, where the familiar algorithm sometimes called the “Four indicator formula” can be used. The present paper is to demonstrate that the complete combinatorial algorithm valid for sets {P _i } not subject to the mentioned restriction opens the path to various results, including the field of Stochastic Geometry. In the paper the complete algorithm is applied first in an integration procedure in a study of the perforated convex domains, i.e convex domains containing a finite array of non-overlapping convex holes. The second application is in the study of random colorings of the plane that are Euclidean motions invariant in distribution, basing on the theory of random polygonal windows from the so-called Independent Angles (IA) class. The method is a direct averaging of the complete combinatorial decompositions written for colorings observed in polygonal windows from the IA class. The approach seems to be quite general, but promises to be especially effective for the random coloring generated by random Poisson polygon process governed by the Haar measure on the group of Euclidean motions of the plane, assuming that a point P ∈ ?² is colored J if P is covered by exactly J polygons of the Poisson process. A general theorem clearing the way for Laplace transform treatment of the random colorings induced on line segments is formulated.