Zone formation problems on embedded planar graphs
Bryan Raymond Stutzman · SMARTech Repository (Georgia Institute of Technology) · 1992
When a planar graph is embedded, the resulting drawing of vertices and edges divides the plane into a set of areas called regions. If the graph is of the road network of a state, the regions could represent political precincts or census tracts. Alternatively, the graph could represent the layout of a microchip or the input of discerned line segments from a robot's camera. This thesis is concerned with combining regions into connected collections called zones. Our work is divided into four parts. The first part develops data structures for the problem and contains algorithms for listing (1) all of the regions of a graph, (2) the maximal (with respect to number of regions) zones that can be formed from a subset of the regions, and (3) all of the possible zones that can be formed on a graph. The last algorithm in this part results in a method for enumerating all cycles on a graph. The second part contains algorithms that form an optimal enclosure around a set of vertices on a graph including a procedure that improves upon those of Provan and also Bienstock and Monma for finding a shortest enclosing walk around an obstacle. The remaining parts are concerned with partitioning a graph into more than one zone. The third part develops measures of the size of the zone and contains a polynomial algorithm for partitioning a graph into two zones to minimize perimeter. The last part discusses heuristic frameworks for finding good solutions for those problems which are NP-hard. Our motivation arose from the problems of electronic mapping, geographic information systems, graph theory, and logistics. Application areas include political districting, delivery routing, service zone formation, VLSI design, and robot vision. A survey of relevant research is included.