Thirty Essays on Geometric Graph Theory

In the mathematical literature, the term “geometric graph theory” is often used in a somewhat vague sense: to cover any area of graph theory in which geometric methods seem to be relevant to the study of graphs defined by geometric means. In the present volume, by a

geometric graph

we mean a graph drawn in the plane so that its vertices are represented by distinct points and its edges by (possibly crossing) straight-line segments between these points such that no edge passes through a vertex different from its endpoints.

Topological graphs

are defined analogously, except that their edges can be represented by simple Jordan arcs [17].

The calculation of the rectilinear crossing number of complete graphs is an important open problem in combinatorial geometry, with important and fruitful connections to other classical problems. Our aim in this chapter is to survey the body of knowledge around this parameter.

Mathematics Subject Classification (2010):

52C30, 52C10, 52C45, 05C62, 68R10, 60D05, 52A22

Let

$$t(\mathcal{C})$$

be the number of tangent pairs among a set

$$\mathcal{C}$$

of

n

Jordan regions in the plane. Pach et al. [Tangencies between families of disjoint regions in the plane, in

Proceedings of the 26th ACM Symposium on Computational Geometry (SoCG 2010)

, Snowbird, June 2010, pp. 423–428] showed that if

$$\mathcal{C}$$

consists of convex bodies and its

intersection graph

is bipartite, then

$$t(\mathcal{C}) \leq 4n - \Theta (1)$$

, and, moreover, there are such sets that admit at least

$$3n - \Theta (\sqrt{n})$$

tangencies. We close this gap and generalize their result by proving that the correct bound is

$$3n - \Theta (1)$$

, even when the intersection graph of

$$\mathcal{C}$$

is only assumed to be triangle-free.

This paper studies problems related to visibility among points in the plane. A point

xblocks

two points

v

and

w

if

x

is in the interior of the line segment

$$\overline{vw}$$

. A set of points

P

is

k-blocked

if each point in

P

is assigned one of

k

colors, such that distinct points

v

,

w

∈

P

are assigned the same color if and only if some other point in

P

blocks

v

and

w

. The focus of this paper is the conjecture that each

k

-blocked set has bounded size (as a function of

k

). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterize all sets

$$\{{n}_{1},{n}_{2},{n}_{3},{n}_{4}\}$$

such that some 4-blocked set has exactly

n

i

points in the

i

th color class. Among other results, for infinitely many values of

k

, we construct

k

-blocked sets with

k

1. 79

…

points.

It is known that for any set

V

of

n

≥ 4 points in the plane, not in convex position, there is a 3-connected planar straight line graph

G

= (

V

,

E

) with at most 2

n

− 2 edges, and this bound is the best possible. We show that the upper bound |

E

| ≤ 2

n

continues to hold if

G

= (

V

,

E

) is constrained to contain a given graph

G

0

= (

V

,

E

0

), which is either a 1-factor (i.e., disjoint line segments) or a 2-factor (i.e., a collection of simple polygons), but no edge in

E

0

is a proper diagonal of the convex hull of

V

. Since there are 1- and 2-factors with

n

vertices for which any 3-connected augmentation has at least 2

n

− 2 edges, our bound is nearly tight in these cases. We also examine possible conditions under which this bound may be improved, such as when

G

0

is a collection of interior-disjoint convex polygons in a triangular container.

Let

P

be a set of

n

points in the plane. A

topological hypergraphG

, on the set of points of

P

, is a collection of simple closed curves in the plane that avoid the points of

P

. Each of these curves is called an

edge

of

G

, and the points of

P

are called the

vertices

of

G

. We provide bounds on the number of edges of topological hypergraphs in terms of the number of their vertices under various restrictions assuming the set of edges is a family of pseudo-circles.

Let

P

be a set of points in the plane in general position. Any three points

$$x,y,z \in P$$

determine a triangle

$$\Delta (x,y,z)$$

of the plane. We say that

$$\Delta (x,y,z)$$

is empty if its interior contains no element of

P

. In this chapter, we study the following problems: What is the size of the largest family of edge-disjoint triangles of a point set? How many triangulations of

P

are needed to cover all the empty triangles of

P

? We also study the following problem: What is the largest number of edge-disjoint triangles of

P

containing a point

q

of the plane in their interior? We establish upper and lower bounds for these problems.

A set

S

of

n

points is

2-color universal

for a graph

G

on

n

vertices if, for every proper 2-coloring of

G

and for every 2-coloring of

S

with the same sizes of color classes as

G

,

G

is straight-line embeddable on

S

.

We show that the so-called double-chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other.

A 2-coloring of

G

is

equitable

if the sizes of the color classes differ by at most 1. A bipartite graph is

equitable

if it admits an equitable proper coloring. We study the case when

S

is the double-chain with chain sizes differing by at most 1 and

G

is an equitable bipartite graph. We prove that this

S

is not 2-color universal if

G

is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half nonleaf vertices. We also show that if this

S

is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.

In this chapter, we survey algorithms and bounds for constructing planar drawings of graphs in a small area.

The crossing-angle resolution of a drawing of a graph measures the smallest angle formed by any pair of crossing edges. In this chapter, we survey some of the most recent results and discuss the current research agenda on drawings of graphs with good crossing-angle resolution.

Leo Moser asked what is the region of largest area that can be moved around a right-angled corner in a corridor of unit width? Similarly, what is the region of largest area that can be reversed in a

T

junction made up of roads of unit width? Can a specific 3-dimensional object pass through a given door? Our survey aims at showing that mover problems are no less challenging even if there are no obstacles other than the objects themselves, but there are many objects to move. We survey some recent results on motion planning and reconfiguration for systems of multiple objects and for modular systems with applications in robotics, and collect some open problems coming out of this line of research.

In the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular drawings, the corners of the rectangles represent the vertices. The graph obtained by taking the rectangles as vertices and contacts as edges is the rectangular dual. In visibility graphs and segment contact graphs, the vertices correspond to horizontal or to horizontal and vertical segments of the dissection. Special orientations of graphs turn out to be helpful when dealing with characterization and representation questions. Therefore, we look at orientations with prescribed degrees, bipolar orientations, separating decompositions, and transversal structures.

In the second part, we ask for representations by a dissections of a rectangle into squares. We review results by Brooks et al. [The dissection of rectangles into squares. Duke Math J 7:312–340 (1940)], Kenyon [Tilings and discrete Dirichlet problems. Isr J Math 105:61–84 (1998)], and Schramm [Square tilings with prescribed combinatorics. Isr J Math 84:97–118 (1993)] and discuss a technique of computing squarings via solutions of systems of linear equations.

Mathematics Subject Classification (2010):

05C10, 05C62, 52C15.

The disjoint convex obstacle number of a graph

G

is the smallest number

h

such that there is a set of

h

pairwise disjoint convex polygons (obstacles) and a set of

n

points in the plane [corresponding to

V

(

G

))]so that a vertex pair

uv

is an edge if and only if the corresponding segment

$$\overline{uv}$$

does not meet any obstacle.

We show that the disjoint convex obstacle number of an outerplanar graph is always at most 5, and of a bipartite permutation graph at most 4. The former answers a question raised by Alpert, Koch, and Laison. We complement the upper bound for outerplanar graphs with the lower bound of 4.

A drawing of a graph is

x

-

monotone

if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Tóth showed that if a graph has an

x

-monotone drawing in which every pair of edges crosses an even number of times, then the graph has an

x

-monotone embedding in which the

x

-coordinates of all vertices are unchanged. We give a new proof of this result and strengthen it by showing that the conclusion remains true even if adjacent edges are allowed to cross each other oddly. This answers a question posed by Pach and Tóth. We show that a further strengthening to a “removing even crossings” lemma is impossible by separating monotone versions of the crossing and the odd crossing number.

Our results extend to level-planarity, which is a well-studied generalization of

x

-monotonicity. We obtain a new and simple algorithm to test level-planarity in quadratic time, and we show that

x

-monotonicity of edges in the definition of level-planarity can be relaxed.

A

geometric graph

is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. A geometric graph contains a

(k,l)-crossing family

if there is a pair of edge subsets

E

1

,

E

2

such that |

E

1

| =

k

and |

E

2

| =

l

, the edges in

E

1

are pairwise crossing, the edges in

E

2

are pairwise crossing, and every edge in

E

1

is disjoint to every edge in

E

2

. We conjecture that for any fixed

k

,

l

, every

n

-vertex geometric graph with no (

k

,

l

)-crossing family has at most

c

k

,

l

n

edges, where

c

k

,

l

is a constant that depends only on

k

and

l

. In this note, we show that every

n

-vertex geometric graph with no (

k

,

k

)-crossing family has at most

c

k

n

log

n

edges, where

c

k

is a constant that depends only on

k

, by proving a more general result that relates an extremal function of a geometric graph

F

with an extremal function of two completely disjoint copies of

F

. We also settle the conjecture for geometric graphs with no (2, 1)-crossing family. As a direct application, this implies that for any circle graph

F

on three vertices, every

n

-vertex geometric graph that does not contain a matching whose intersection graph is

F

has at most

O

(

n

) edges.

We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set

S

of points in the plane to

pseudo-simultaneously flippable edges

. Such edges are related to the notion of convex decompositions spanned by

S

.

We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of

N

points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let

$$\mathsf{tr}(N)$$

denote the maximum number of triangulations on a set of

N

points in the plane. Then we show [using the known bound

$$\mathsf{tr}(N) < 3{0}^{N}$$

] that any

N

-element point set admits at most

$$6.928{3}^{N} \cdot \mathsf{tr}(N) < 207.8{5}^{N}$$

crossing-free straight-edge graphs,

$$O(4.702{2}^{N}) \cdot \mathsf{tr}(N) = O(141.0{7}^{N})$$

spanning trees, and

$$O(5.351{4}^{N}) \cdot \mathsf{tr}(N) = O(160.5{5}^{N})$$

forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have

cN

, fewer than

cN

, or more than

cN

edges, for any constant parameter

c

, in terms of

c

and

N

.

Graph augmentation problems are motivated by network design and have been studied extensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geometric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems.

We consider some problems on red and blue points in the plane lattice. An

L

-line segment in the plane lattice consists of a vertical line segment and a horizontal line segment having a common endpoint. There are some results on geometric graphs on a set of red and blue points in the plane. We show that some similar results also hold for a set of red and blue points in the plane lattice using

L

-line segments instead of line segments. For example, we show that if

n

red points and

n

blue points are given in the plane lattice in general position, then there exists a noncrossing geometric perfect matching covering them, each of whose edges is an

L

-line segment and connects a red point and a blue point.

We survey some results and collect a set of open problems related to graph Ramsey theory with geometric constraints.

In this chapter, we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs and, in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: Being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.

A

circle graph

is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number

k

is

$$50 \cdot {2}^{k}$$

. We prove a stronger bound of 2

k

−1 for graphs in a simpler subclass of circle graphs, called

clean graphs

. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.

In a convex

n

-gon, let

$${d}_{1} > {d}_{2} > \cdots $$

denote the set of all distances between pairs of vertices, and let

m

i

be the number of pairs of vertices at distance

d

i

from one another. Erdős, Lovász, and Vesztergombi conjectured that

$$\sum\nolimits_{i\leq k}{m}_{i} \leq kn$$

. Using a new computational approach, we prove their conjecture when

k

≤ 4 and

n

is large; we also make some progress for arbitrary

k

by proving that

$$\sum\nolimits_{i\leq k}{m}_{i} \leq (2k - 1)n$$

. Our main approach revolves around a few known facts about distances, together with a computer program that searches all distance configurations of two disjoint convex hull intervals up to some finite size. We thereby obtain other new bounds, such as

m

3

≤ 3

n

∕2 for large

n

.

In this chapter, we discuss two classical problems lying on the edge of graph theory and combinatorial geometry. The first problem is due to E. Nelson. It consists of coloring metric spaces in such a way that pairs of points at some prescribed distances receive different colors. The second problem is attributed to K. Borsuk and involves finding the minimum number of parts of smaller diameter into which an arbitrary bounded nonsingleton point set in a metric space can be partitioned. Both problems are easily translated into the language of graph theory, provided we consider, instead of the whole space, any (finite) distance graph or any (finite) graph of diameters. During the last decades, a huge number of ideas have been proposed for solving both problems, and many results in both directions have been obtained. In the survey below, we try to give an entire picture of this beautiful area of geometric combinatorics.

We show that deciding whether a graph with given edge lengths can be realized by a straight-line drawing has the same complexity as deciding the truth of sentences in the existential theory of the real numbers,

ETR

; we introduce the class

$$\exists \mathbb{R}$$

that captures the computational complexity of

ETR

and many other problems. The graph realizability problem remains

$$\exists \mathbb{R}$$

-complete if all edges have unit length, which implies that recognizing unit distance graphs is

$$\exists \mathbb{R}$$

-complete. We also consider the problem for

linkages

: In a realization of a linkage, vertices are allowed to overlap and lie on the interior of edges. Linkage realizability is

$$\exists \mathbb{R}$$

-complete and remains so if all edges have unit length. A linkage is called

rigid

if any slight perturbation of its vertices that does not break the linkage (i.e., keeps edge lengths the same) is the result of a rigid motion of the plane. Testing whether a configuration is not rigid is

$$\exists \mathbb{R}$$

-complete.

If

X

is a Minkowski space, i.e., a finite-dimensional real normed space, then

$$S \subset X$$

is an equilateral set if all pairs of points of

S

determine the same distance with respect to the norm. Kusner conjectured that

$$e({\mathcal{l}}_{p}^{d}) = d + 1$$

for

$$1 < p < \infty $$

and

$$e({\mathcal{l}}_{1}^{d}) = 2d$$

[6]. Using a technique combining linear algebra and approximation theory, we prove that for all

$$1 < p < \infty $$

, there exists a constant

C

p

> 0 such that

$$e({\mathcal{l}}_{p}^{d}) \leq {C}_{p}{d}^{1+2/(p-1)}$$

.

In this note, we prove several Turán-type results on geometric hypergraphs. The two main theorems are (1) every

n

-vertex geometric 3-hypergraph in the plane with no three strongly crossing edges has at most

O

(

n

2

) edges, and (2) every

n

-vertex geometric 3-hypergraph in 3-space with no two disjoint edges has at most

O

(

n

2

) edges. These results support two conjectures that were raised by Dey and Pach, and by Akiyama and Alon.

Let

S

be a set of

n

points in

$${\mathbb{R}}^{d}$$

. Assign to each

x

∈

S

an arbitrary distance

r

(

x

) > 0. Let

e

r

(

x

,

S

) denote the number of points in

S

at distance

r

(

x

) from

x

. Avis, Erdős, and Pach (1988) introduced the extremal quantity

$${f}_{d}(n) =\max \sum\limits_{\mathbf{x}\in S}{e}_{r}(\mathbf{x},S)$$

, where the maximum is taken over all

n

-point subsets

S

of

$${\mathbb{R}}^{d}$$

and all assignments

$$r: S \rightarrow (0,\infty )$$

of distances.

We give a quick derivation of the asymptotics of the error term of

f

d

(

n

) using only the analogous asymptotics of the maximum number of unit distance pairs in a set of

n

points:

$${f}_{d}(n) = \left(1 - \frac{1} {\lfloor d/2\rfloor }\right){n}^{2}+\left\{\begin{array}{@{}l@{\quad }l@{}} \Theta (n) \quad &\text{ if}\ d\ \text{ is even,} \\ \Theta {((n/d))}^{4/3})\quad &\text{ if}\ d\ \text{ is odd.} \end{array} \right.$$

The implied constants are absolute. This improves on previous results of Avis, Erdős, and Pach (1988) and Erdős and Pach (1990).

Then we prove a stability result for

d

≥ 4, asserting that if (

S

,

r

) with

$$\left\vert S\right\vert = n$$

satisfies

$${e}_{r}(S) = {f}_{d}(n) - o({n}^{2})$$

, then, up to

o

(

n

) points,

S

is a Lenz construction with

r

constant. Finally, we use stability to show that for

n

sufficiently large (depending on

d

), the pairs (

S

,

r

) that attain

f

d

(

n

) are up to scaling exactly the Lenz constructions that maximize the number of unit distance pairs with

r

≡ 1, with some exceptions in dimension 4.

Analogous results hold for the furthest-neighbor digraph, where

r

is fixed to be

$$r(\mathbf{x}) {=\max }_{\mathbf{y}\in S}\vert \mathbf{x}\mathbf{y}\vert$$

for

x

∈

S

.

The task of this survey is to present various results on intersection patterns of convex sets. One of the main tools for studying intersection patterns is a point of view via simplicial complexes. We recall the definitions of so-called

d

-representable,

d

-collapsible, and

d

-Leray simplicial complexes, which are very useful for this study. We study the differences among these notions and also focus on computational complexity for recognizing them. A list of Helly-type theorems is presented in the survey. We also discuss the important role played by the above-mentioned notions for the theorems. We also consider intersection patterns of good covers, which generalize collections of convex sets (the sets may be “curvy”; however, their intersections cannot be too complicated). We mainly focus on new results.

Mathematics Subject Classification (2010):

primary 52A35, secondary 05E45, 52A20

A graph drawn in the plane with straight-line edges is called a geometric graph. If no path of length at most

k

in a geometric graph

G

is self-intersecting, we call

Gk

-locally plane. The main result of this chapter is a construction of

k

-locally plane graphs with a superlinear number of edges. For the proof, we develop randomized thinning procedures for edge-colored bipartite (abstract) graphs that can be applied to other problems as well.

The crossing number

cr

(

G

) of a graph

G

is the minimum possible number of edge crossings in a drawing of

G

, and the pair-crossing number

pair-cr

(

G

) is the minimum possible number of crossing pairs of edges in a drawing of

G

. Clearly, pair-cr(

G

) ≤ cr(

G

). We show that for any graph

G

,

$$\mathrm{cr}(G) = O(\text{ pair-cr}{(G){}^{7/4}\log }^{3/2}(\text{ pair-cr}(G)))$$

.

This is an expository chapter based on two talks given during the Special Semester on Discrete and Computational Geometry, organized by János Pach and Emo Welzl, at the École Polytechnique Fédérale in Lausanne, Switzerland, in the fall of 2010.

Our first purpose is to describe a circle of ideas regarding topological

extremal problems

for simplicial complexes (hypergraphs), and the corresponding

phase-transition

questions for

random complexes

(as introduced by Linial and Meshulam). In particular, we discuss some notions of

minors

pertaining to such questions. Our focus is on

k

-dimensional complexes that are

sparse

, i.e., such that the number of

k

-dimensional simplices is linear in the number of (

k

− 1)-dimensional simplices.

Second, we discuss a notion of higher-dimensional

expansion

for simplicial complexes, due to Gromov, which is very useful in this context (the same notion of expansion has also arisen independently in the work of Linial, Meshulam, and Wallach on random complexes, and in the work of Newman and Rabinovich on higher-dimensional analogues of finite metrics).