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.
Octilinear drawings form a natural extension of the so-called , which allow for horizontal and vertical edge segments only. For such drawings, the bend minimization problem can be solved efficiently, assuming that the input is an embedded graph @cite_12 . However, the corresponding minimization problem over all embeddings of the input graph is NP-hard @cite_1 . Note that in @cite_12 the author describes how one can extend his approach, so to compute a bend-optimal octilinear representation Recall that a representation of a graph describes the angles and the bends of a drawing, neglecting its exact geometry @cite_12 . of any given embedded @math -planar graph. However, such a representation may not be realizable by a corresponding planar octilinear drawing @cite_17 .
@cite_1 @cite_12 @cite_17
2012855423 1594340659 2508647357 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. Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing . This paper initiates the study of combinatorial and algorithmic questions related with the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed. 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 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.