A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> Line-of-sight graphs were introduced by Garey, Johnson and So in connection with a circuit testing problem. A restricted version of the problem (using line segments and a single line-of-sight) is discussed and the associated graphs are characterized. Results for directed and weighted cases are also presented. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub-configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> A bar layout is a set of vertically oriented non-intersecting line segments in the plane called bars. The visibility graph associated with a layout is defined as the graph whose vertices correspond to the bars and whose edges represent the horizontal visibilities between pairs of bars. ::: This dissertation is concerned with the characterization of bar-representable graphs: those graphs which are the visibility graphs of some bar layout. A polynomial time algorithm for determining if a given graph is bar-representable, and the subsequent construction of an associated layout are provided. Weighted and directed versions of the problem are also formulated and solved; in particular, polynomial time algorithms for the layout of such graphs are developed. ::: The Planar Full Flow problem is to determine a plane embedding and an (acyclic) orientation of an undirected planar network that admits a feasible flow, that uses all arcs (except those incident upon the source or sink) to full capacity and maintains planarity. The connection of this flow problem to bar-representable graphs is exploited to solve the weighted case of the latter. As evidence that the problem is inherently difficult, two natural variants of the Full Flow problem are shown to be strongly NP-Complete. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence between vertices of G and bars in S, such that there is an edge between two vertices in G if and only if there exists an unobstructed vertical line of sight between their corresponding bars. If bars are allowed to see through each other, the graphs representable in this way are precisely the interval graphs. We consider representations in which bars are allowed to see through at most k other bars. Since all bar visibility graphs are planar, we seek measurements of closeness to planarity for bar k-visibility graphs. We obtain an upper bound on the number of edges in a bar k-visibility graph. As a consequence, we obtain an upper bound of 12 on the chromatic number of bar 1-visibility graphs, and a tight upper bound of 8 on the size of the largest complete bar 1-visibility graph. We also consider the thickness of bar k-visibility graphs, obtaining an upper bound of 4 when k = 1, and a bound that is quadratic in k for k > 1. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> A visibility representation is a classical drawing style of planar graphs. It displays the vertices of a graph as horizontal vertex-segments, and each edge is represented by a vertical edge-segment touching the segments of its end vertices; beyond that segments do not intersect. We generalize visibility to 1-visibility, where each edge- (vertex-) segment crosses at most one vertex- (edge-) segment. In other words, a vertex is crossed by at most one edge, and vice-versa. We show that 1-visibility properly extends 1-planarity and develop a linear time algorithm to compute a 1-visibility representation of an embedded 1-planar graph on O(n^2) area. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. Concerning density, both 1-visible and 1-planar graphs of size $n$ have at most 4n-8 edges. However, for every n>= 7 there are 1-visible graphs with 4n-8 edge which are not 1-planar. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> Abstract A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex. We show that every IC-plane graph has a visibility drawing where every vertex is of the form { ? , ? , ? , ? } , and every edge is either a horizontal or vertical segment. As a byproduct of our drawing technique, we prove that every IC-plane graph has a RAC drawing in quadratic area with at most two bends per edge. We study visibility representations of IC-planar graphs.We show that every IC-planar graph has an L-visibility drawing in quadratic area which can be computed in linear time.We prove that every IC-planar graph has a RAC drawing in quadratic area with at most two bends per edge. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> We study contact representations of graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We show that for every 3-connected planar graph, there exists a simultaneous representation of the graph and its dual with 3D boxes. We give a linear-time algorithm for constructing such a representation. This result extends the existing primal-dual contact representations of planar graphs in 2D using circles and triangles. While contact graphs in 2D directly correspond to planar graphs, we next study representations of non-planar graphs in 3D. In particular we consider representations of optimal 1-planar graphs. A graph is 1-planar if there exists a drawing in the plane where each edge is crossed at most once, and an optimal n-vertex 1-planar graph has the maximum (4n - 8) number of edges. We describe a linear-time algorithm for representing optimal 1-planar graphs without separating 4-cycles with 3D boxes. However, not every optimal 1-planar graph admits a representation with boxes. Hence, we consider contact representations with the next simplest axis-aligned 3D object, L-shaped polyhedra. We provide a quadratic-time algorithm for representing optimal 1-planar graph with L-shaped polyhedra. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be $$\varOmega (n)$$ Ω(n) . In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> A $1$-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A NIC-plane graph is a $1$-plane graph such that any two pairs of crossing edges share at most one end-vertex. An edge partition of a $1$-plane graph $G$ is a coloring of the edges of $G$ with two colors, red and blue, such that both the graph induced by the red edges and the graph induced by the blue edges are plane graphs. We prove the following: $(i)$ Every NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree three; this bound on the vertex degree is worst-case optimal. $(ii)$ Deciding whether a $1$-plane graph admits an edge partition such that the red graph has maximum vertex degree two is NP-complete. $(iii)$ Deciding whether a $1$-plane graph admits an edge partition such that the red graph has maximum vertex degree one, and computing one in the positive case, can be done in quadratic time. Applications of these results to graph drawing are also discussed. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> We prove that every 1-planar graph G has a z-parallel visibility representation, i.e., a 3D visibility representation in which the vertices are isothetic disjoint rectangles parallel to the xy-plane, and the edges are unobstructed z-parallel visibilities between pairs of rectangles. In addition, the constructed representation is such that there is a plane that intersects all the rectangles, and this intersection defines a bar 1-visibility representation of G. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> A (weak) rectangle visibility representation, or simply an RVR, of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Given a graph with a fixed embedding in the plane, we show that the problem of testing whether this graph has an embedding-preserving RVR can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs, i.e., for embedded graphs having at most one crossing per edge. The linear time algorithm uses three forbidden configurations, which extend the set known for straight-line drawings of 1-plane graphs. The algorithm first checks for the presence of these forbidden configurations in the input graph, and then either an embedding-preserving RVR is computed (also in linear time) or a forbidden configuration is reported as a negative witness. Finally, we discuss extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> An ortho-polygon visibility representation $\Gamma$ of a $1$-plane graph $G$ (OPVR of $G$) is an embedding preserving drawing that maps each vertex of $G$ to a distinct orthogonal polygon and each edge of $G$ to a vertical or horizontal visibility between its end-vertices. The representation $\Gamma$ has vertex complexity $k$ if every polygon of $\Gamma$ has at most $k$ reflex corners. It is known that $3$-connected $1$-plane graphs admit an OPVR with vertex complexity at most twelve, while vertex complexity at least two may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity five is always sufficient, while vertex complexity four may be required in some cases. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in $3$-connected $1$-plane graphs. An implication of the upper bound is the existence of a $\tilde{O}(n^\frac{10}{7})$-time drawing algorithm that computes an OPVR of an $n$-vertex $3$-connected $1$-plane graph on an integer grid of size $O(n) \times O(n)$ and with vertex complexity at most five. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> Number of bends per edge <s> Abstract A topological graph is a graph drawn in the plane. A topological graph is k -plane, k > 0 , if each edge is crossed at most k times. We study the problem of partitioning the edges of a k -plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for k = 1 , we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests. <s> BIB014
Δ denotes the maximum vertex degree. The question mark indicates that no area bound is known. on the other hand, every planar graph admits this representation 3 (see, e.g.,  BIB001 ). In order to realize nonplanar graphs, other visibility models have been proposed, such as bar k-visibility representations and rectangle visibility representations. In a bar k-visibility representation, each visibility intersects at most k bars BIB004 . In particular, it is proved that every 1-planar graph has a bar 1-visibility representation BIB005  . A rectangle visibility representation maps each vertex to an axis-aligned rectangle and each edge to a horizontal or vertical visibility between the two corresponding rectangles  BIB003 . In general, there are 1-plane graphs, and even IC-plane graphs, that do not admit such a representation. Biedl et al. describe a linear-time algorithm to test whether a 1-plane graph admits an embedding-preserving rectangle visibility representation and to compute one if it exists BIB012 . The algorithm is based on a characterization that extends the set of obstructions used by Thomassen to characterize the stretchable 1-plane graphs BIB002 . The rectangle visibility model has been recently generalized to extend the class of representable graphs; namely, in a generalized model, called ortho-polygon visibility representations, the vertices are drawn as general orthogonal polygons BIB009 . Di Giacomo et al. prove that every 1-plane graph admits an embedding-preserving ortho-polygon visibility representation BIB009 . If the input graph is 3-connected, one can construct a representation such that each vertex has at most 12 reflex corners, while 2 reflex corners may be needed. If the graph is only 2-connected, it may require at least one vertex with a linear number of reflex corners. The upper bound for 3-connected 1-plane graphs exploits results on edge partitions (see also BIB014 BIB010 BIB006 ). The gap for 3-connected 1-plane graphs has been recently reduced, proving that at most 5 reflex corners per vertex always suffice, while 4 reflex corners are needed in some cases BIB013 . A further visibility model, called L-visibility representations, maps every vertex to a horizontal and a vertical segment sharing an endpoint (i.e., by an L-shape in the set { , û , ú }), and each edge to a horizontal or vertical visibility segment joining the two L-shapes corresponding to its two end-vertices. It is proved that every IC-planar graph admits an L-visibility representation BIB007 . Visibility representations of 1-planar graphs have been studied also in 3D. A z-parallel visibility representation maps the vertices of a graph to isothetic disjoint rectangles parallel to the xy-plane and the edges to visibilities parallel to the z-axis. Every 1-plane graph has a z-parallel visibility representation BIB011 . The computed drawing is such that there is a plane orthogonal to the rectangles of the representation, and the intersection of this plane with the representation defines a bar 1-visibility representation of the graph. Finally, Alam et al. studied contact representations in which vertices are represented by axisaligned polyhedra in 3D and edges are realized by non-zero area common boundaries between × indicates that there are instances of the graph family not admitting that visibility or contact representation. means that all instances in the graph family can be drawn with that visibility or contact representation. The question mark means that it not known whether the answer is × or . LEGEND: RVR = rectangle visibility representation, B1VR = bar 1-visibility representation, k OPVR = ortho-polygon visibility representation, LVR = L-visibility representation, ZPR = z-parallel visibility representation, BCR = box contact representation, LCR = L-shaped contact representation. corresponding polyhedra BIB008 . They prove that every optimal 1-plane graph can be realized as a contact representation where vertices are axis-aligned boxes if it contains no separating 4-cycles or as a contact representation where vertices are L-shaped polyhedra otherwise. Table 7 summarizes the main results on visibility and contact representations of 1-planar graphs.