Minimum cuts in geometric intersection graphs

摘要

Let D be a set of n disks in the plane. The disk graph G(D) for D is the undirected graph with vertex set D in which two disks are joined by an edge if and only if they intersect. The directed transmission graph G -> D for D is the directed graph with vertex set Din which there is an edge from a disk D-1 is an element of D to a disk D-2 is an element of D if and only if D-1 contains the center of D-2.