Modeling Graph Problems

Proper modeling is the key to making effective use of graph algorithms. We have seen a variety of definitions of graph properties, and algorithms for computing them. All told, about two dozen different graph problems are presented in the catalog, mostly in Sections and . These problems provide a framework for modeling most applications.  

The applications below demonstrate the power of proper modeling. Each of them arose in a real-world application as stated, and each can be modeled as a graph problem. Some of the modelings are quite clever, but they illustrate the versatility of graphs in representing relationships. As you read the problem, try to devise an appropriate graph representation before peeking to see how we did it.

• ``I'm looking for an algorithm to design natural routes for video-game characters to follow through an obstacle-filled room. How should I do it?''  

  Presumably the route that is wanted is the path that looks most like the one that an intelligent being would choose. Since intelligent beings are either lazy or efficient, this should be modeled as some kind of shortest path problem.

  But what is the graph? One approach would be to lay a grid of points in the room and have a vertex for each point that is a valid place for the character to stand, i.e. so it does not lie within an obstacle. There will be an edge between any pair of nearby vertices, weighted according to the distance between them. The shortest path between two vertices will be close to the shortest path between the points. Although direct geometric methods are known for shortest paths (see Section ), it is easier to model this discretely as a graph.  

• ``In DNA sequencing, we are given experimental data consisting of small fragments. For each fragment f, we have certain other fragments that are forced to lie to the left of f, certain fragments forced to be to the right of f, and the remaining fragments, which are free to go on either side. How can we find a consistent ordering of the fragments from left to right that satisfies all the constraints?''     

  Create a directed graph, where each fragment is assigned a unique vertex. Insert a directed edge from any fragment l that is forced to be to the left of f, and a directed edge to any fragment r forced to be to the right of f. We seek an ordering of the vertices such that all the edges go from left to right. This is exactly a topological sort of the resulting directed acyclic graph. The graph must be acyclic for this to work, because cycles make finding a consistent ordering impossible.

• ``In my graphics work I need to solve the following problem. Given an arbitrary set of rectangles in the plane, how can I distribute them into a minimum number of buckets such that the subset of rectangles in the same bucket do not intersect each other? In other words, there should not be any overlapping area between any two rectangles in the same bucket.''     

  We can formulate a graph where each vertex is a rectangle, and there is an edge if two rectangles intersect. Each bucket corresponds to an independent set of rectangles, so there is no overlap between any two. A vertex coloring of a graph is a partition of the vertices into independent sets, so minimizing the number of colors is exactly what you want.

• ``In porting code from UNIX to DOS, I have to shorten the names of several hundred files down to at most 8 characters each. I can't just take the first eight characters from each name, because ``filename1'' and ``filename2'' will get assigned the exact same name. How can I shorten the names while ensuring that they do not collide?''   

  Construct a graph with vertices corresponding to each original file name for , as well as a collection of acceptable shortenings for each name . Add an edge between each original and shortened name. Given such a formulation, we seek a set of n edges that have no vertices in common, because the file name of each is thus mapped to a distinct acceptable substitute. Bipartite matching, discussed in Section , is exactly this problem of finding an independent set of edges in a graph.  

• ``In organized tax fraud, criminals submit groups of phony tax returns in the hopes of getting undeserved refunds. These phony returns are all similar, but not identical. How can we detect clusters of similar forms so the IRS can nail the cheaters?''  

  A natural graph model treats each form as a vertex and adds an edge between any two tax forms that are suspiciously similar. A cluster would correspond to a group of forms with many edges between them. In particular, a clique is a set of k vertices with all possible edges between them. Any sufficiently large clique identifies a cluster worth studying.   

• ``In the optical character-recognition system that we are building, we need a way to separate the lines of text. Although there is some white space between the lines, problems like noise and the tilt of the page makes it hard to find. How can we do line segmentation?     

  Consider the following graph formulation. Treat each pixel in the image as a vertex in the graph, with an edge between two neighboring pixels. The weight of this edge should be proportional to how dark the pixels are. A segmentation between two lines is a path in this graph from the left to right side of the page. Of all possible paths, we seek a relatively straight path that avoids as much blackness as possible. This suggests that the shortest path in the pixel graph will likely find a good line segmentation.