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>
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received December 18, 1995, and in revised form June 17, 1997.
Rights and permissions
About this article
Cite this article
Katchalski, M., Last, H. On Geometric Graphs with No Two Edges in Convex Position . Discrete Comput Geom 19, 399–404 (1998). https://doi.org/10.1007/PL00009357
Issue Date:
DOI: https://doi.org/10.1007/PL00009357