Abstract. A geometric graph is a graph
G=G(V,E) drawn in the plane, where its vertex set
V is a set of points in general position and its edge set
E consists of straight segments whose endpoints belong to
V . Two edges of a geometric graph are in convex position if they are disjoint edges of a convex quadrilateral. It is proved
here that a geometric graph with
n vertices and no edges in convex position contains at most
2n-1 edges. This almost solves a conjecture of Kupitz. The proof relies on a projection method (which may have other applications)
and on a simple result of Davenport—Schinzel sequences of order 2.
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p399.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>