Abstract

A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges g,e1,...ekg,e_1,...e_k, such that e1,e2,...eke_1,e_2,...e_k have a common endpoint and gg crosses all eie_i. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.