✦ LIBER ✦

On the intersection of edges of a geometric graph by straight lines

✍ Scribed by N. Alon; M.A. Perles

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 969 KB
Volume: 60
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90004-x

No coin nor oath required. For personal study only.

✦ Synopsis

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 ( = egg) if V is the set of vertices of a convex polygon. For n 3 1, 0 se c (;) and m Z= 1 let )) be the maximal number such that for every gg (egg) G with n vertices and e edges there exists a set of m lines whose union intersects at least 2 (I,) edges of G. In this paper we determine Z,(n, e, m) precisely for all admissible n, e and m and show that Z(n, e, m) = Z,(n, e, m) if 2me > n2 and in many other cases.

📜 SIMILAR VOLUMES

On a straight-line embedding problem of

On a straight-line embedding problem of graphs

✍ Shin-ichi Tokunaga 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane ~2 in general position. A straight-line embeddin9 of G onto P is an embedding of G onto R 2 whose images of vertices are distinct points in P and whose images of edges are (straig

Edge intersection graphs of single bend

Edge intersection graphs of single bend paths on a grid

✍ Martin Charles Golumbic; Marina Lipshteyn; Michal Stern 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

On the intersection rank of a graph

✍ James A. Wiseman 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 748 KB

Wiseman, J.A., On the intersection rank of a graph, Discrete Mathematics 104 293-305.

Covering the Edges of a Connected Graph

Covering the Edges of a Connected Graph by Paths

✍ L. Pyber 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 316 KB

We prove that every connected graph on n vertices can be covered by at most nÂ2+O(n 3Â4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.

Further remarks on partitioning the edge

Further remarks on partitioning the edges of a graph

✍ A.J.W Hilton; Rhys Price Jones 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 80 KB

On Number of Circles Intersected by a Li

On Number of Circles Intersected by a Line

✍ Lu Yang; Jingzhong Zhang; Weinian Zhang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 394 KB