Abstract.
A geometric graph is a graph G=(V,E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight-line segments between points of V . Two edges of a geometric graph are said to be parallel if they are opposite sides of a convex quadrilateral.
In this paper we show that, for any fixed k ≥ 3 , any geometric graph on n vertices with no k pairwise parallel edges contains at most O(n) edges, and any geometric graph on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. We also prove a conjecture by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n-2 edges. <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>19n3p461.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 January 27, 1997, and in revised form March 4, 1997, and June 16, 1997.
Rights and permissions
About this article
Cite this article
Valtr, P. On Geometric Graphs with No k Pairwise Parallel Edges . Discrete Comput Geom 19, 461–469 (1998). https://doi.org/10.1007/PL00009364
Issue Date:
DOI: https://doi.org/10.1007/PL00009364