Strongly connected orientations of plane graphs (Q1759876)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Strongly connected orientations of plane graphs |
scientific article |
Statements
Strongly connected orientations of plane graphs (English)
0 references
22 November 2012
0 references
The purpose of the paper is to orient a subset of edges of a given plane graph such that the resulting subgraph is strongly connected and spans all vertices of the graph. In addition, the number of oriented arcs is minimum and at the same time produces a digraph with smallest possible stretch factor. The paper also presents three constructions for such orientations.
0 references
digraph
0 references
directional antennae
0 references
plane graph
0 references
sensors
0 references
cut edges
0 references
spanner
0 references
stretch factor
0 references
strongly connected subgraps
0 references
edge orientation
0 references
number of oriented arcs
0 references
