### Abstract

A geometric graph ( = gg) is a pair G = 〈V, E〉, where V is a finite set of points ( = vertices) in general position in the plane, and E is a set of open straight line segments ( = edges) whose endpoints are in V. G is a convex gg ( = cgg) if V is the set of vertices of a convex polygon. For n≥1, 0≤e≤(^{n}_{2}) and m≥1 let I = I(n,e,m) (I_{c}=I_{c}(n,e,m)) be the maximal number such that for every gg (cgg) G with n vertices and e edges there exists a set of m lines whose union intersects at least I (I_{c}) edges of G. In this paper we determine I_{c}(n,e,m) precisely for all admissible n, e and m and show that I(n,e,m) = I_{c}(n,e,m) if 2me≥n^{2} and in many other cases.

Original language | English (US) |
---|---|

Pages (from-to) | 75-90 |

Number of pages | 16 |

Journal | Discrete Mathematics |

Volume | 60 |

Issue number | C |

DOIs | |

State | Published - Jan 1 1986 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'On the intersection of edges of a geometric graph by straight lines'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Perles, M. A. (1986). On the intersection of edges of a geometric graph by straight lines.

*Discrete Mathematics*,*60*(C), 75-90. https://doi.org/10.1016/0012-365X(86)90004-X