In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and ...In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H.展开更多
1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the inte...1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the intersection of a horizontal segment and a verticalsegment of an edge. A planar graph G is κ-rectilinear if it admits a plane embedding Gwhich is a κ-bend graph. In this case G is said to be a κ-embedding of G.展开更多
文摘In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H.
文摘1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the intersection of a horizontal segment and a verticalsegment of an edge. A planar graph G is κ-rectilinear if it admits a plane embedding Gwhich is a κ-bend graph. In this case G is said to be a κ-embedding of G.
