A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> The haloed line effect is a technique where when a line in three-dimensional space passes in front of another line, a gap is produced in the projection of the more distant line. The gap is produced as if an opaque halo surrounded the closer line. This method for approximate hidden-line-elimination is advantageous because explicit surface equations are not necessary. The relative depth of lines, axes, curves and lettering is easily perceived. This technique is especially suitable for the display of finite element grids, three-dimensional contour maps and ruled surfaces. When the lines or curves on a surface are closer than the gap size, the gaps produced close up to produce a complete hidden-line-elimination. A simple but efficient implementation is described which can be used in the rendering of a variety of three-dimensional situations. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Networks are critical to modern society, and a thorough understanding of how they behave is crucial to their efficient operation. Fortunately, data on networks is plentiful; by visualizing this data, it is possible to greatly improve our understanding. Our focus is on visualizing the data associated with a network and not on simply visualizing the structure of the network itself. We begin with three static network displays; two of these use geographical relationships, while the third is a matrix arrangement that gives equal emphasis to all network links. Static displays can be swamped with large amounts of data; hence we introduce direct manipulation techniques that permit the graphs to continue to reveal relationships in the context of much more data. In effect, the static displays are parameterized so that interesting views may easily be discovered interactively. The software to carry out this network visualization is called SeeNet. > <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Let G be a topological graph on n vertices in the plane, i.e., a graph drawn in the plane with its vertices represented as points and its edges represented as Jordan arcs connecting pairs of points. It is shown that if no two edges of any cycle of length 4 in G cross an odd number of times, then |E(G)|=O(n8/5). <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n log n). This result is asymptotically tight. Analogous questions for longer forbidden paths and for graphs drawn by not necessarily straight-line edges are also considered. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Edge casing is a well-known method to improve the readability of drawings of non-planar graphs. A cased drawing orders the edges of each edge crossing and interrupts the lower edge in an appropriate neighborhood of the crossing. Certain orders will lead to a more readable drawing than others. We formulate several optimization criteria that try to capture the concept of a ''good'' cased drawing. Further, we address the algorithmic question of how to turn a given drawing into an optimal cased drawing. For many of the resulting optimization problems, we either find polynomial time algorithms or NP-hardness results. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> One of the main principles for the effective visualization of graphs is the avoidance of edge crossings. Around this problem, very active research has been performed with works ranging from combinatorics, to algorithmics, visualization effects, to psychological user studies. Recently, the pragmatic approach has been proposed to avoid crossings by drawing the edges only partially. Unfortunately, no formal model and efficient algorithms have been formulated to this end. We introduce the concept for drawings of graphs with partially drawn edges (PED). Therefore we consider graphs with and without given embedding and characterize PEDs with concepts like symmetry and homogeneity. For graphs without embedding we formulate a sufficient condition to guarantee a symmetric homogeneous PED, and identify a nontrivial graph class which has a symmetric homogeneous PED. For graphs with given layout we consider the variants of maximizing the shortest partially drawn edge and the total length respectively. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction $\delta$ of the edge lengths ($\delta$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. ::: We show that, for a fixed stub--edge length ratio $\delta$, not all graphs have a $\delta$-SHPED. Specifically, we show that $K_{241}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $\Theta(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Avoiding crossings for reducing visual clutter is one of the main objectives in the area of graph drawing. Apart from work on geometric solutions to this problem, there are radical approaches originating from information visualization in which edges are drawn just partially. Theory on this approach is already established in several directions and 1/4-SHPED arose as standard. A 1/4-SHPED (Symmetric Homogeneous Partial Edge Drawing) is a drawing model in which vertices are drawn as points and edges as two pieces (= stubs) of a straight-line segment, each incident to a vertex, without any crossing stubs, and with stub size 1/4 of the total edge length. If crossings are permitted in a 1/4-SHPED, we call it 1/4-nSHPED (n = nearly). 1/4-nSHPEDs and 1/4-SHPEDs help the reader inferring adjacent vertices by approximating the distance due to four times the stub length. Symmetry of stubs helps to verify adjacency. We describe a force-directed algorithm that aims at producing a 1/4-SHPED. The algorithm is finally evaluated with several classes of graphs. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> Partial Edge Drawing (PED) is a popular graph drawing style aimed at reducing edge crossings and visual clutter. PEDs are straight-line drawings where the central part of each edge is erased, and the length of the two remaining segments are computed so as to preserve useful geometric information. Recent studies on this approach focus on symmetric and δ-homogeneous PEDs (δ-SHPEDs). Given a straight-line drawing, a δ-SHPED of this drawing is immediately defined for a fixed value of δ. In particular, some edge crossings may not be avoidable, although the amount of ink removed from the original drawing might be large (e.g., 50% when δ = 1/4). On the other hand, it is possible to maximize the ink and remove edge crossings by renouncing to homogeneity. We present heuristics to produce symmetric PEDs that are either crossing-free or where crossings forming large angles are allowed. We also describe a user study in which PEDs obtained via our heuristics are compared with the standard model 1/4-SHPED. Our results suggest that the benefit of homogeneity overcomes in terms of readability the benefit of fewer crossings and more ink. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Partial edge drawings (PEDs). <s> We introduce the family of k-gap-planar graphs for \(k \ge 0\), i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition finds motivation in edge casing, as a \(k\)-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs. <s> BIB010
In a Partial Edge Drawing (PED) the "middle" part of each edge is omitted to obtain a crossing-free representation. The idea behind this drawing style was introduced to visualize network overload between switches of the AT&T long-distance telephone network in the United States BIB002 . In particular, in an α-Symmetric Homogeneous PED (SHPED) (0 < α < 1 2 ), each edge (u, v) is (partially) drawn as a pair of segments, called α-stubs, one incident to u, the other incident to v, and each being a fraction α of segment uv; the two stubs do not cross. The α-SHPED model has been formally defined only recently BIB006 and has inspired both theoretical BIB007 and practical research (see, e.g., BIB009 BIB008 ). Bruckdorfer et al. extended this model for graphs with maximum degree four, where the drawings are orthogonal and have at most one bend per edge  . k-gap-planar drawings. In a k-gap-planar drawing it is possible to map each crossing to one of the two corresponding crossing edges so that, for each edge e, at most k crossings are mapped to e. This family generalizes k-planar graphs and was introduced in Bae et al. BIB010 with a practical motivation inspired by edge casing, a method commonly used to alleviate the visual clutter caused by crossing lines BIB001 BIB005 . In a cased drawing of a graph, each crossing is resolved by locally interrupting one of the two crossing edges, and a k-gap-planar graph can be equivalently defined as a graph that admits a cased drawing in which each edge has at most k gaps. H -self-intersecting-free drawings. Given a graph H , a straight-line H -self-intersecting-free (Hsif) drawing does not contain a self-intersecting geometric graph isomorphic to H . This definition specializes the more general H -free drawings, which do not contain graphs isomorphic to H . Typical forbidden configurations consider self-intersecting paths or cycles BIB004 BIB003 , whose study was triggered by classical extremal problems on forbidden geometric subgraphs (see, e.g.,  ).