Suppose you are working for a cartography company, that is, a company that makes maps. Your job is to design a software package that can take as input the map of some region, R, and label as many of the cities of R as possible. Each of the n cities in such a region, R, is given by an (x, y) coordinate for the center of that city. Assume, for the sake of simplifying the problem, that the label, Lc, for each city, c, is a rectangle (which will contain the name of the city, c) whose lower-right corner is the (x, y)-location for c. The labels for two cities, c and d, conflict if Lc intersects Ld. Given your extensive algorithmic background, you realize that you can model this problem with a graph, G, where you create a vertex in G for each city and connect cities c and d with an edge if their labels conflict. Let d = 2m/n be the average degree of the vertices in G, where m is the number of edges in G. Describe an O(d)-approximation algorithm for finding the largest number of mutually nonconflicting labels for the cities in a given region R.