##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 258.05112

**Autor: ** Erdös, Paul; Lovász, László; Simmons, A.; Straus, E.G.

**Title: ** Dissection graphs of planar point sets. (In English)

**Source: ** Survey combin. Theory, Sympos. Colorado State Univ., Colorado 1971, 139- 149 (1973).

**Review: ** [For the entire collection see Zbl 254.00005.]

Let S be a set of n points in general position (no three collinear) in the plane. For any two points p,q in S, the directed line \overrightarrow{pq} has a certain number, N(\overrightarrow{pq}), of points of S on its positive side, that is, the open half plane to the right of \overrightarrow{pq}. We are interested in the direct k-graphs, G_{k}, of S whose edges are the segments \overrightarrow{pq} with N(\overrightarrow{pq}) = k (k = 0,1, ... ,n-2). Since clearly G_{n-k-2} = -G_{k}, that is, the k-graph with all orientations reversed, it suffices to consider the cases k \leq (n-2)/2. If n is even, then the bigraph B = G_{(n-2)/2} is of special interest since each edge occurs in both orientations and it can therefore be considered as an undirected graph. This case has been studied in several previous papers. In Section 2, we discuss some general properties of the graphs G_{k}. In Section 3, we answer the relatively easy question concerning the upper and lower bounds on the number of vertices of G_{k} and the lower bound on the number of edges of G_{k}. In Section 4, we tackle the far more difficult problem of the upper bound e_{n,k} on the number of edges in G_{k}. We obtain upper bounds of the form on \sqrt k and lower bounds of the form on log n for e_{n,rn-1}, where r is a rational number, 0 < r < 1, and rn is an integer. Finally in Section 5 we discuss new problems and generalizations.

**Classif.: ** * 05C20 Directed graphs (digraphs)

52A10 Convex sets in 2 dimensions (including convex curves)

05C99 Graph theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag