In octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal ( @math ) line-segments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A @math -planar graph is a planar graph in which each vertex has degree less or equal to @math . In particular, we prove that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size @math . For 5-planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in super-polynomial area. However, for 6-planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge.
Octilinear drawings can be considered as an extension of , which allow only horizontal and vertical segments (i.e., graphs of maximum degree @math admit such drawings). Tamassia @cite_10 showed that one can minimize the total number of bends in orthogonal drawings of embedded 4-planar graphs. However, minimizing the number of bends over all embeddings of a 4-planar graph is NP-hard @cite_4 . Note that the core of Tamassia's approach is a min-cost flow algorithm that first specifies the angles and the bends of the drawing, producing an , and then based on this representation computes the actual drawing by specifying the exact coordinates for the vertices and the bends of the edges. It is known that Tamassia's algorithm can be employed to produce a bend-minimum octilinear representation for any given embedded 8-planar graph. However, a bend-minimum octilinear representation may not be realizable by a corresponding planar octilinear drawing @cite_17 . Furthermore, the number of bends on a single edge might be very high, but can easily be bounded by applying appropriate capacity constraints to the flow-network.
@cite_10 @cite_4 @cite_17
2012855423 2508647357 2067795681 2117205241
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. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+Δ) bits. There is an inherent tradeoff between the sparsity parameter Δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when Δ ≥ 1 3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when Δ In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter Δ ∈ (0,1 3). Specifically, for any integer k ≥ 2, any compression scheme with size [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−1 k). This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ϵ, β)-spanners have an essentially optimal tradeoff between Δ, ϵ, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ϵ, O(k ϵ)k−1)-spanners with size [EQUATION], where hk Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ϵ)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent. 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 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.