Intersection Graphs
Alan Frieze, Michał Karoński · Cambridge University Press eBooks · 2023
A graph is an intersection graph if we assign to each vertex a set from some family S so that there is an edge between two of its vertices when respective sets intersect. Depending on the choice of family S, often reflecting some geometric configuration, one can consider, for example, interval graphs defined as the intersection graphs of intervals on the real line, unit disk graphs defined as the intersection graphs of unit disks on the plane, etc. In this chapter, we will discuss properties of random intersection graphs, where the family S is generated in a random manner. In this chapter, we discuss the properties of binomial intersection random graphs and random geometric graphs.