The Setting
A vertex cover of a graph is a designated set of its vertices that meets every edge. The crossing bounds here concern straight-line drawings with such a cover, with constants depending on both the size of the cover and the number of vertices.
Planar points , and belong to .✦ For three planar points, the orientation determinant is (1)✦ A finite configuration , indexed by a finite set , is in general position if its points are distinct and the determinant in (1) is nonzero for every three distinct indices. A finite configuration has distinct first coordinates if whenever .
A straight-line drawing on consists of a finite vertex set and a finite edge set , with each edge directed from left to right: (2)✦ Each edge in (2) is drawn as the segment joining its endpoint points. Let be a designated vertex cover of .
The open segment of an edge is the set (3) Two edges cross if their open segments from (3) intersect.✦ A crossing pair of is an unordered pair of distinct edges that cross, and is the number of these pairs.✦ Write for the vertex count, for the edge count, and for the size of the designated cover.
The Claim
Theorem 1. Let be a finite configuration in general position with distinct first coordinates. Let be a straight-line drawing on , and let be a vertex cover of . The designated-endpoint crossing bound (4) holds: (4)✦ If , the dense bound (5) holds: (5)✦
In the paper, the result reads: for a simple graph with a straight-line drawing on distinct points, with no vertex in an edge interior and no crossings of incident edges, if every edge has an endpoint in a specified set of at most vertices, then , where is the edge count and counts properly crossing edge pairs, and if , then .
What Is Checked
The bounds are stated over finite straight-line drawings satisfying (2), on configurations in general position with distinct first coordinates, with a designated vertex cover and crossings defined by intersection of open edge segments.