Strongly connected orientations of plane graphs (Q1759876)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Strongly connected orientations of plane graphs |
scientific article; zbMATH DE number 6109942
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Strongly connected orientations of plane graphs |
scientific article; zbMATH DE number 6109942 |
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
0.8625116944313049
0 references
0.7923960089683533
0 references
0.7853639125823975
0 references
0.7671636939048767
0 references
0.7544617652893066
0 references
