An octilinear drawing of a planar graph is one in which each edge is drawn as a sequence of horizontal, vertical and diagonal at 45 degrees line-segments. For such drawings to be readable, special care is needed in order to keep the number of bends small. As the problem of finding planar octilinear drawings of minimum number of bends is NP-hard, in this paper we focus on upper and lower bounds. From a recent result of on the slope number of planar graphs, we can derive an upper bound of 4n-10 bends for 8-planar graphs with n vertices. We considerably improve this general bound and corresponding previous ones for triconnected 4-, 5- and 6-planar graphs. We also derive non-trivial lower bounds for these three classes of graphs by a technique inspired by the network flow formulation of Tamassia.
For orthogonal drawings, several bounds on the total number of bends are known. Biedl @cite_9 presents lower bounds for graphs of maximum degree @math based on their connectivity (simply connected, biconnected or triconnected), planarity (planar or not) and simplicity (simple or non-simple with multiedges or selfloops). It is also known that any @math -planar graph (except for the octahedron graph) admits a planar orthogonal drawing with at most two bends per edge @cite_0 @cite_15 . Trivially, this yields an upper bound of @math bends, which can be improved to @math @cite_0 . Note that the best known lower bound is due to @cite_2 , who presented @math -planar graphs requiring @math bends.
@cite_0 @cite_9 @cite_2 @cite_15
2117205241 1568439834 2067795681 2012855423
Abstract An orthogonal drawing of a graph is an embedding in the plane such that all edges are drawn as sequences of horizontal and vertical segments. Linear time and space algorithms for drawing biconnected planar graphs orthogonally with at most 2n + 4 bends on a grid of size n × n are known in the literature. In this paper we generalize this result to connected and non-planar graphs. Moreover, we show that in almost all cases each edge is bent at most twice. The algorithm handles both planar and non-planar graphs at the same time. An orthogonal drawing is an embedding of a graph such that edges are drawn as sequences of horizontal and vertical segments. In this paper we explore lower bounds. We find lower bounds on the number of bends when crossings are allowed, and lower bounds on both the grid-size and the number of bends for planar and plane drawings. Abstract We study planar orthogonal drawings of graphs and provide lower bounds on the number of bends along the edges. We exhibit graphs on n vertices that require Ω( n ) bends in any layout, and show that there exist optimal drawings that require Ω( n ) bends and have all of them on a single edge of length Ω( n 2 ). This work finds applications in VLSI layout, aesthetic graph drawing, and communication by light or microwave. Abstract In this paper we describe a linear algorithm for embedding planar graphs in the rectilinear two-dimensional grid, where vertices are grid points and edges are noncrossing grid paths. The main feature of our algorithm is that each edge is guaranteed to have at most 2 bends (with the single exception of the octahedron for which 3 bends are needed). The total number of bends is at most2 n + 4 if the graph is biconnected and at most(7 3) n in the general case. The area is( n + 1) 2 in the worst case. This problem has several applications to VLSI circuit design, aesthetic layout of diagrams, computational geometry.