Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Moreover, we show that the search space of the best coverage problem can be confined to the relative neighborhood graph, which can be constructed locally. In addition, we justify the correctness of the method proposed in that uses the Delaunay triangulation to solve the best coverage problem.
PLANAR DISK GRAPH PROOF CITESEE HOW TO
We also consider how to find an optimum best-coverage-path that travels a small distance. As energy conservation is a major concern in wireless (or sensor) networks, we also consider how to find an optimum bestcoverage -path with the least energy consumption. Here, we consider the sensing model: the sensing ability diminishes as the distance increases. In this paper, we give efficient distributed algorithms to optimally solve the best-coverage problem raised in. In, it is assumed that the sensor has the uniform sensing ability. One of the fundamental problems in sensor networks is the calculation of the coverage. A biconnected component of G is a maximal biconnected subgraph of G.Sensor networks pose a number of challenging conceptual and optimization problems such as location, deployment, and tracking. G is biconnected if G is connected and has no cut vertex. However, if we modify forest F in the figure by replacing edge has more connected components than G. For example, in Figure 1.1, G is a plane embedding of G satisfying F. Nonleaf vertex f of F, the interior of the curve J f corresponding to f contains all the leaf descendants of f in F but contains no other leaves of F. (The dotted curves are the required Jordan curves.) A plane graph G, a rooted forest F, and a different embedding G of G satisfying F. 3 Department of Computer Science and Engineering, State Univeristy of New York at Buffalo, Buffalo, NY 14260, USA. Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan. The research of the second author was supported in part by NSF Grant CCR-9912418. A plane embedding G of G satisfies F if there are |VF | − |V | pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of F such that for every 1 Let (G, F) be a planar-graph forest (PGF) pair, i.e., a pair of a planar graph G = (V, E) and a rooted forest F = (VF, AF ) such that V is also the set of the leaves of F. In this paper we initiate the study of the following new planarity problem. Note that two noncrossing Jordan curves may share a point. Two Jordan curves cross if both the interior and the exterior of each curve contain a point of the other curve. The closure of the interior of J is called the closed interior of J. The bounded and the unbounded regions are called the interior and the exterior of J, respectively. This set consists of two topologically connected regions one region is bounded while the other is not. Consider the set of all points in the plane that do not lie on J. A Jordan curve is a continuous non-self-intersecting curve in the plane whose origin and terminus coincide. This planarity problem can be solved in linear time. A classical variant of the problem is to test whether a given graph is planar and in case it is, to find a planar embedding. (Throughout this paper, a graph may have multiple edges but may never have self-loops, while a simple graph never has either.) A graph is planar if it can be embedded on the plane so that any pair of edges can only intersect at their endpoints a plane graph is a planar one together with such an embedding. It is a fundamental problem in mathematics (e.g., see, ,, ,, and ) to embed a graph into a given surface while optimizing certain objectives required by applications. Graph algorithm, Planar graph, Planar embedding.ġ. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex f in F induces a connected subgraph of G. It is unknown whether this problem can be solved in polynomial time. This problem arises from theoretical studies in geographic database systems. Given a planar graph G = (V, E) and a rooted forest F = (VF, AF ) with leaf set V, we wish to decide whether G has a plane embedding G satisfying the following condition: There are |VF | − |V | pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of F such that for every nonleaf vertex f of F, the interior of the curve J f corresponding to f contains all the leaf descendants of f in F but contains no other leaves of F. Algorithmica (2004) 38: 539–576 DOI: 10.1007/s0045-0ĭisk Embeddings of Planar Graphs1 Zhi-Zhong Chen2 and Xin He3 Abstract.
0 kommentar(er)
