A Survey on Graph Drawing Beyond Planarity <s> Problem 12. Does every topological graph of maximum vertex degree three admit an embeddingpreserving straight-line RAC drawing? <s> We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Problem 12. Does every topological graph of maximum vertex degree three admit an embeddingpreserving straight-line RAC drawing? <s> 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. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Problem 12. Does every topological graph of maximum vertex degree three admit an embeddingpreserving straight-line RAC drawing? <s> We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. <s> BIB003
Finally, we recall that a characterization of the almost-plane graphs that are stretchable is known only when the number of edges is 3n − 5 (a characterization for nonmaximal is known on the sphere but not in the plane) BIB001 . Hence, a natural question is the following: Problem 13. Characterize the topological skewness-k graphs that are stretchable. This question is interesting also when k = 1 and the number of edges is smaller than 3n − 5. Several open problems can also be deduced by looking at the "?" in Tables 6, 7, and 8. For example: Problem 14. It is known that every 1-planar graph has a RAC drawing with at most one bend per edge BIB002 . However, it is not known whether such a drawing can be computed in polynomial area. Regarding this problem, it has been recently shown that NIC-plane graphs admit an embeddingpreserving 1-bend RAC drawing in quadratic area BIB003 .