Coloring Intersection Graphs of Arc-Connected Sets in the Plane

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line \(L\) if the intersection of any member with \(L\) is a nonempty segment. It is proved that the intersection graphs of simple families of compact arc-connected sets in the plane pierced by a common line have chromatic number bounded by a function of their clique number.     

On the Connectivity of Visibility Graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71?C93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)??deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ? collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$ , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ?=4 we improve this bound to two thirds of the minimum degree.     

Visibility Graphs and Oriented Matroids

   Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

Visibility Graphs and Oriented Matroids

Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

A General Notion of Visibility Graphs

Abstract. We define a natural class of graphs by generalizing prior notions of visibility, allowing the representing regions and sightlines to be arbitrary. We consider mainly the case of compact connected representing regions, proving two results giving necessary properties of visibility graphs, and giving some examples of classes of graphs that can be so represented. Finally, we give some applications of the concept, and we provide potential avenues for future research in the area.     

A General Notion of Visibility Graphs

   Abstract. We define a natural class of graphs by generalizing prior notions of visibility, allowing the representing regions and sightlines to be arbitrary. We consider mainly the case of compact connected representing regions, proving two results giving necessary properties of visibility graphs, and giving some examples of classes of graphs that can be so represented. Finally, we give some applications of the concept, and we provide potential avenues for future research in the area.     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

Characterizing Starshaped Sets by Maximal Visibility

Let S be a nonempty set in a real topological linear space L. p S is a point of maximal visibility of S if and only if it admits a neighbourhood N in L such that Sq Sp for every point q S N, where Sx = { s S : x is visible from s via S }. For S being either open and connected or the closure of its connected interior, it is shown that the kernel of S is the set of all maximal visibility points of S. Planar examples reveal that the topological assumptions on S are necessary. This substantially strengthens a recent result of Toranzos and Forte Cunto.     

L-Regularity of Markov Sets and of m-Perfect Sets in the Complex Plane

Let E be a compact subset of C. We prove that if E satisfies the following local Markov property: for each polynomial P,

Sets of Locally Maximal Visibility and Finite Unions of Starshaped Sets

 Let , where is an open connected subset of some linear topological space, such that S contains all triangular regions whose (relative) boundaries lie in S. If some finite subset T of S has locally maximal visibility in S, then . Hence S is a finite union of starshaped sets whose kernels are determined by T. An analogous result holds for S open. Moreover, counterexamples show that neither the requirement on triangular regions nor the restriction to a finite set T can be deleted. (Received 7 September 1998; in revised form 25 October 1999)     

Box-Rectangular Drawings of Plane Graphs

In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists.     

Polychromatic Colorings of Plane Graphs

We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is -complete. Research of N. Alon was supported in part by the Israel Science Foundation, by a USA–Israeli BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research of R. Berke was supported in part by JSPS Global COE program “Computationism as a Foundation for the Sciences.” Research of K. Buchin and M. Buchin was supported by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS project no. 642.065.503. Research of P. Csorba was supported by DIAMANT, an NWO mathematics cluster. Research of B. Speckmann was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.022.707.     

Perfect Partitions of Convex Sets in the Plane

   Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Perfect Partitions of Convex Sets in the Plane

Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Convex Sets in Lexicographic Products of Graphs

Geodesic convex sets, Steiner convex sets, and J-convex (alias induced path convex) sets of lexicographic products of graphs are characterized. The geodesic case in particular rectifies Theorem 3.1 in Canoy and Garces (Graphs Combin 18(4):787–793, 2002).