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
2063120809 1483246560
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. 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. A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams. We show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an @math error for any @math . A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with @math , a straight-line embedding on a grid of size @math can be computed deterministically in @math time with @math processors. If randomization is used, the complexity is improved to @math expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.