In this paper, we introduce and study "geometric simultaneous RAC drawing problems", i.e., a combination of problems on geometric RAC drawings and geometric simultaneous graph drawings. To the best of our knowledge, this is the first time where such a combination is attempted.
@cite_8: Recent cognitive experiments have shown that the negative impact of an edge crossing on the human understanding of a graph drawing, tends to be eliminated in the case where the crossing angles are greater than 70 degrees. This motivated the study of RAC drawings, in which every pair of crossing edges intersects at right angle. In this work, we demonstrate a class of graphs with unique RAC combinatorial embedding and we employ members of this class in order to show that it is NP-hard to decide whether a graph admits a straight-line RAC drawing.
@cite_9: We study how much better a right-angled crossing (RAC) drawing of a planar graph can be than any planar drawing of the same planar graph. We analyze the area requirement, the edge-length ratio, and the angular resolution. For the first two measures, a RAC drawing can be arbitrarily much better, whereas for the third measure a RAC drawing can be 2.75 times as good.
@cite_6: We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of
@cite_3: Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing . This paper initiates the study of combinatorial and algorithmic questions related with the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed.
@cite_0: A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of @p2. In this paper we provide a characterization of the complete bipartite graphs that admit a straight-line RAC drawing.
@cite_5: A Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1-planar graph is a graph that has a drawing where every edge is crossed at most once. We study the relationship between RAC graphs and 1-planar graphs in the extremal case that the RAC graphs have as many edges as possible. It is known that a maximally dense RAC graph with n>3 vertices has 4n --- 10 edges. We show that every maximally dense RAC graph is 1-planar. Also, we show that for every integer i such that i≥0, there exists a 1-planar graph with n=8+4i vertices and 4n --- 10 edges that is not a RAC graph.
@cite_10: In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area.
@cite_12: Right Angle Crossing (RAC) drawings are polyline drawings where each crossing forms four right angles. RAC drawings have been introduced because cognitive experiments provided evidence that increasing the number of crossings does not decrease the readability of the drawing if the edges cross at right angles. We investigate to what extent RAC drawings can help in overcoming the limitations of widely adopted planar graph drawing conventions, providing both positive and negative results. First, we prove that there exist acyclic planar digraphs not admitting any straight-line upward RAC drawing and that the corresponding decision problem is NP-hard. Also, we show digraphs whose straight-line upward RAC drawings require exponential area. Second, we study if RAC drawings allow us to draw bounded-degree graphs with lower curve complexity than the one required by more constrained drawing conventions. We prove that every graph with vertex-degree at most 6 (at most 3) admits a RAC drawing with curve complexity 2 (resp. 1) and with quadratic area. Third, we consider a natural non-planar generalization of planar embedded graphs. Here we give bounds for curve complexity and area different from the ones known for planar embeddings.
@cite_3 were the first to study the geometric RAC drawing problem and proved that any graph with @math vertices that admits a geometric RAC drawing has at most @math edges. @cite_6 presented bounds on the number of edges of polyline RAC drawings with at most one or two bends per edge. @cite_12 presented acyclic planar digraphs that do not admit upward geometric RAC drawings and proved that the corresponding decision problem is @math -hard. @cite_8 proved that it is @math -hard to decide whether a given graph admits a geometric RAC drawing (i.e., the upwardness requirement is relaxed). Di @cite_10 presented tradeoffs on the maximum number of bends per edge, the required area and the crossing angle resolution. @cite_0 characterized classes of complete bipartite graphs that admit geometric RAC drawings. Van Kreveld @cite_9 showed that the quality of a planar drawing of a planar graph (measured in terms of area required, edge-length and angular resolution) can be improved if one allows right-angle crossings. Eades and Liotta @cite_5 proved that a (i.e., @math ) is also @math -planar, i.e., it admits a drawing in which every edge is crossed at most once.