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
2018091581 2002025203 1986266847
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 . Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time @math , where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of @math degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams. We connect two aspects of graph drawing, namely angular resolution, and the possibility to draw with all angles an integer multiple of 2π d. A planar graph with angular resolution at least π 2c an be drawn with all angles an integer multiple of π 2 (rectilinear). For d =4 , d> 2, an angular resolution of 2π d does not imply that the graph can be drawn with all angles an integer multiple of 2π d. We argue that the exceptional situation for d = 4 is due to the absence of triangles in the rectangular grid.