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
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references