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, Gk, of S whose edges are the segments \overrightarrow{pq} with N(\overrightarrow{pq}) = k (k = 0,1, ... ,n-2). Since clearly Gn-k-2 = -Gk, 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 Gk. In Section 3, we answer the relatively easy question concerning the upper and lower bounds on the number of vertices of Gk and the lower bound on the number of edges of Gk. In Section 4, we tackle the far more difficult problem of the upper bound en,k on the number of edges in Gk. We obtain upper bounds of the form on \sqrt k and lower bounds of the form on log n for en,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