On Embedding a Graph in the Grid with the Minimum Number of Bends (Q3801098)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4068320
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On Embedding a Graph in the Grid with the Minimum Number of Bends |
scientific article; zbMATH DE number 4068320 |
Statements
On Embedding a Graph in the Grid with the Minimum Number of Bends (English)
0 references
1987
0 references
planar embedding
0 references
rectilinear grid
0 references
bends
0 references
network flow
0 references
VLSI circuit layout
0 references
0.8493409156799316
0 references
0.8398822546005249
0 references
0.8308852910995483
0 references
0.8299389481544495
0 references
Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time \(O(n^ 2 \log n)\), where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of 180/k degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams.
0 references