2010 | OriginalPaper | Buchkapitel
Strong Orientations of Planar Graphs with Bounded Stretch Factor
verfasst von : Evangelos Kranakis, Oscar Morales Ponce, Ladislav Stacho
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of orienting some edges of given planar graph such that the resulting subdigraph is strongly connected and spans all vertices of the graph. We are interested in orientations with minimum number of arcs and such that they produce a digraph with bounded stretch factor. Such orientations have applications into the problem of establishing strongly connected sensor network when sensors are equipped with directional antennae.
We present three constructions for such orientations. Let
G
= (
V
,
E
) be a connected planar graph without cut edges and let Φ(
G
) be the degree of largest face in
G
. Our constructions are based on a face coloring, say with
λ
colors. First construction gives a strong orientation with at most
$\left( 2 - \frac{4 \lambda - 6}{\lambda (\lambda - 1)} \right) |E|$
arcs and stretch factor at most Φ(
G
) − 1. The second construction gives a strong orientation with at most |
E
| arcs and stretch factor at most
$(\Phi (G) - 1)^{\lceil \frac{\lambda + 1}{2} \rceil}$
. The third construction can be applied to planar graphs which are 3-edge connected. It uses a particular 6-face coloring and for any integer
k
≥ 1 produces a strong orientation with at most
$\left(1 - \frac{k}{10 (k + 1)}\right) |E|$
arcs and stretch factor at most Φ
2
(
G
) (Φ(
G
) − 1)
2
k
+ 4
. These are worst-case upper bounds. In fact the stretch factors depend on the faces being traversed by a path.