Premium
On planar intersection graphs with forbidden subgraphs
Author(s) -
Pach János,
Sharir Micha
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20332
Subject(s) - combinatorics , mathematics , intersection graph , bipartite graph , logarithm , exponent , intersection (aeronautics) , regular polygon , graph , planar graph , upper and lower bounds , discrete mathematics , line graph , geometry , mathematical analysis , linguistics , philosophy , engineering , aerospace engineering
Let ${\cal C}$ be a family of n compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with k vertices in each of its classes. Then $G({\cal C})$ has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k . In the case where ${\cal C}$ consists of convex sets, we improve this bound to O ( n log n ). If in addition k = 2, the bound can be further improved to O ( n ). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom