On Embedding a Graph in the Grid with the Minimum Number of Bends

Citations Over TimeTop 10% of 1987 papers

Abstract

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.

Related Papers

• → A survey on book-embedding of planar graphs(2022)5 cited
• → Minimum Depth Graph Embedding(2000)12 cited
• → On simultaneous straight-line grid embedding of a planar graph and its dual(2006)3 cited
• → Regular Augmentation of Planar Graphs(2014)4 cited
• → Planarity Testing and Optimal Edge Insertion with Embedding Constraints(2007)3 cited