On Disjoint Crossing Families in Geometric Graphs

Radoslav Fulek () and Andrew Suk ()
Additional contact information
Radoslav Fulek: Ecole Polytechnique Fédérale de Lausanne
Andrew Suk: Massachusetts Institute of Technology (MIT), Department of Mathematics

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 289-302 from Springer

Abstract: Abstract A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. A geometric graph contains a (k,l)-crossing family if there is a pair of edge subsets E 1, E 2 such that | E 1 | = k and | E 2 | = l, the edges in E 1 are pairwise crossing, the edges in E 2 are pairwise crossing, and every edge in E 1 is disjoint to every edge in E 2. We conjecture that for any fixed k, l, every n-vertex geometric graph with no (k, l)-crossing family has at most c k, l n edges, where c k, l is a constant that depends only on k and l. In this note, we show that every n-vertex geometric graph with no (k, k)-crossing family has at most c k nlogn edges, where c k is a constant that depends only on k, by proving a more general result that relates an extremal function of a geometric graph F with an extremal function of two completely disjoint copies of F. We also settle the conjecture for geometric graphs with no (2, 1)-crossing family. As a direct application, this implies that for any circle graph F on three vertices, every n-vertex geometric graph that does not contain a matching whose intersection graph is F has at most O(n) edges.

Keywords: Geometric Graphs; Circle Graphs; Intersection Graph; Edge Subset; Simple Topological Graph (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_15

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().