The thickness of a graph @math with @math vertices is the minimum number of planar subgraphs of @math whose union is @math . A polyline drawing of @math in @math is a drawing @math of @math , where each vertex is mapped to a point and each edge is mapped to a polygonal chain. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of @math is the maximum number of bends per edge in @math , and the layer complexity of @math is the minimum integer @math such that the set of polygonal chains in @math can be partitioned into @math disjoint sets, where each set corresponds to a planar polyline drawing. Let @math be a graph of thickness @math . By F ' a ry's theorem, if @math , then @math can be drawn on a single layer with bend complexity @math . A few extensions to higher thickness are known, e.g., if @math (resp., @math ), then @math can be drawn on @math layers with bend complexity 2 (resp., @math ). However, allowing a higher number of layers may reduce the bend complexity, e.g., complete graphs require @math layers to be drawn using 0 bends per edge. In this paper we present an elegant extension of F ' a ry's theorem to draw graphs of thickness @math . We first prove that thickness- @math graphs can be drawn on @math layers with @math bends per edge. We then develop another technique to draw thickness- @math graphs on @math layers with bend complexity, i.e., @math , where @math . Previously, the bend complexity was not known to be sublinear for @math . Finally, we show that graphs with linear arboricity @math can be drawn on @math layers with bend complexity @math .
Given an @math -vertex planar graph @math and a point location for each vertex in @math , Pach and Wenger @cite_11 showed that @math admits a planar polyline drawing with the given vertex locations, where each edge has at most @math bends. They also showed that @math bends are sometimes necessary. @cite_3 and Gordon @cite_4 independently improved the bend complexity to @math . Consequently, for @math , these constructions can be used to draw @math on @math layers with at most @math bends per edge.
@cite_4 @cite_3 @cite_11
2053608598 98352059 2067795681 2048913517 2624658792 2012855423 2063120809 1438552389 1868235818 1772951445 2057352080 1575929063 1594340659 2809995963 2143699278 2052977033 1992898832 1770850069 2761681115 2569784685
We consider graphs that admit polyline drawings where all crossings occur at the same angle @math . We prove that every graph on @math vertices that admits such a polyline drawing with at most two bends per edge has @math edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. In this paper, we study the problem of drawing a given planar graph such that vertices are at pre-specified points and the entire drawing is inside a given polygon. We give a method that shows that for an n-vertex graph and a k-sided polygon, Θ(kn2) bends are always sufficient. We also give an example of a graph where Θ(kn2) bends are necessary for such a drawing. 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. Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G^'@?G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G^'. We concentrate on trees and show how to compute the output in O(n^2logn) time in a real-RAM model and with at most n-k edges with at most [email protected]?k [email protected]? bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k-3 bends on n-k edges. Abstract A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. 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. Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V"0,...,V"k"-"1 for some positive integer [email protected][email protected]?n. Let S be a set of n distinct points in the plane with a partition into subsets S"0,...,S"k"-"1 with |V"i|=|S"i| ([email protected][email protected]?k-1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of V"i is mapped to a distinct point of S"i. Lower and upper bounds on the number of bends per edge are proved for any [email protected][email protected]?n. In the special case k=n, we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717-728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. This paper describes algorithms for computing non-planar drawings of planar graphs in subquadratic area such that: (i) edge crossings are allowed only if they create large angles; (ii) the maximum number of bends per edge is bounded by a (small) constant. We give an algorithm to create orthogonal drawings of 3- connected 3-regular planar graphs such that each interior face of the graph is drawn with a prescribed area. This algorithm produces a drawing with at most 12 corners per face and 4 bends per edge, which improves the previous known result of 34 corners per face. In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area. In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area. The simultaneous embedding problem is, given two planar graphs G1=(V,E1) and G2=(V,E2), to find planar embeddings ϕ(G1) and ϕ(G2) such that each vertex v∈V is mapped to the same point in ϕ(G1) and in ϕ(G2). This article presents a linear-time algorithm for the simultaneous embedding problem such that edges are drawn as polygonal chains with at most two bends and all vertices and all bends of the edges are placed on a grid of polynomial size. An extension of this problem with so-called fixed edges is also considered A further linear-time algorithm of this article solves the following problem: Given a planar graph G and a set of distinct points, find a planar embedding for G that maps each vertex to one of the given points. The solution presented also uses at most two bends per edge and a grid whose size is polynomial in the size of the grid that includes all given points. An example shows two bends per edge to be optimal 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. An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1 k ). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1 k ) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1 k ) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more). Right Angle Crossing (RAC) drawings are polyline drawings where each crossing forms four right angles. RAC drawings have been introduced because cognitive experiments provided evidence that increasing the number of crossings does not decrease the readability of the drawing if the edges cross at right angles. We investigate to what extent RAC drawings can help in overcoming the limitations of widely adopted planar graph drawing conventions, providing both positive and negative results. First, we prove that there exist acyclic planar digraphs not admitting any straight-line upward RAC drawing and that the corresponding decision problem is NP-hard. Also, we show digraphs whose straight-line upward RAC drawings require exponential area. Second, we study if RAC drawings allow us to draw bounded-degree graphs with lower curve complexity than the one required by more constrained drawing conventions. We prove that every graph with vertex-degree at most 6 (at most 3) admits a RAC drawing with curve complexity 2 (resp. 1) and with quadratic area. Third, we consider a natural non-planar generalization of planar embedded graphs. Here we give bounds for curve complexity and area different from the ones known for planar embeddings. Given a planar triangulated graph (PTG) G, the problem of constructing a floor-plan F such that G is the dual of F and the boundary of F is rectangular is studied. It is shown that if only zero-concave rectilinear modules (CRM) (or rectangular modules) and 1-CRM (i.e., L-shaped) are allowed, there are PTGs that do not admit any floor-plan. However, if 2-bend modules (e.g., T-shaped and Z-shaped) are also allowed, then every biconnected PTG admits a floor-plan. Thus, the employment of 2-bend modules is necessary and sufficient for graph dualization floor-planning. A linear-time algorithm for constructing a 2-CRM floor-plan of an arbitrary PTG is proposed. The bend-numberb(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We confirm a conjecture of Biedl and Stern showing that the maximum bend-number of outerplanar graphs is 2. Moreover we improve the formerly known lower and upper bound for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively. We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of Abstract In this paper we continue the study of the edge intersection graphs of single bend paths on a rectangular grid (i.e., the edge intersection graphs where each vertex is represented by one of the following shapes: ⌞ , ⌜ , ⌟ , ⌝ ). These graphs, called B 1 - EPG graphs, were first introduced by (2009) [Golumbic, M. C., M. Lipshteyn and M. Stern, Edge intersection graphs of single bend paths on a grid , Networks 54 :3 (2009), 130–138]. We focus on the class [⌞] (the edge intersection graphs of ⌞-shapes) and show that testing for membership in [⌞] is NP-complete. We then give a characterization and polytime recognition algorithm for special subclasses of Split ∩ [ ⌞ ] . We also consider the natural subclasses of B 1 -EPG formed by the subsets of the four single bend shapes (i.e., ⌞ , ⌞ , ⌜ , ⌞ , ⌝ , ⌞ , ⌜ , ⌝ – note: all other subsets are isomorphic to these up to 90 degree rotation). We observe the expected strict inclusions and incomparability (i.e., [ ⌞ ] ⊊ [ ⌞ , ⌜ ] , [ ⌞ , ⌝ ] ⊊ [ ⌞ , ⌜ , ⌝ ] ⊊ B 1 -EPG and [ ⌞ , ⌜ ] is incomparable with [ ⌞ , ⌝ ] ).