Premium
Route discovery with constant memory in oriented planar geometric networks
Author(s) -
Chávez E.,
Dobrev S.,
Kranakis E.,
Opatrny J.,
Stacho L.,
Urrutia J.
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20114
Subject(s) - vertex (graph theory) , planar graph , planar , routing (electronic design automation) , computer science , face (sociological concept) , combinatorics , constant (computer programming) , eulerian path , spatial network , topology (electrical circuits) , graph , mathematics , theoretical computer science , discrete mathematics , computer network , pure mathematics , social science , computer graphics (images) , sociology , programming language , lagrangian
We address the problem of discovering routes in strongly connected planar geometric networks with directed links. Motivated by the necessity for establishing communication in wireless ad hoc networks in which the only information available to a vertex is its immediate neighborhood, we are considering routing algorithms that use the neighborhood information of a vertex for routing with constant memory only. We solve the problem for three types of directed planar geometric networks: Eulerian (in which every vertex has the same number of incoming and outgoing edges), Outerplanar in which a single face contains all vertices of the network, and Strongly Face Connected, a new class of geometric networks that we define in the article, consisting of several faces, each face being a strongly connected outerplanar graph. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 7–15 2006