Search

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. [ABSTRACT FROM AUTHOR]

Abstract: Mixed graphs have both directed and undirected edges and have received considerable attention in the literature. We study two upward planarity testing problems for embedded mixed graphs, give some NP-hardness results, and describe Integer Linear Programming techniques to solve them. Experiments show the efficiency of our approach. [Copyright &y& Elsevier]

Abstract: In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in area using a sub-linear number of crossings per edge, and that for any given number , every outerplanar graph admits an area drawing with crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of series–parallel graphs with bounded vertex-degree. [Copyright &y& Elsevier]

Abstract: The crossing resolution of a geometric graph is the minimum crossing angle at which any two edges cross each other. In this paper, we present upper and lower bounds to the crossing resolution of the complete geometric graphs. [Copyright &y& Elsevier]

Abstract: 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 to 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. [Copyright &y& Elsevier]

Abstract: Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of . We concentrate on trees and show how to compute the output in time in a real-RAM model and with at most edges with at most bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least bends on edges. [Copyright &y& Elsevier]

Abstract: Let G be an embedded planar digraph. A maximum upward planar subgraph of G is an embedding preserving subgraph that is upward planar and, among those, has the maximum number of edges. This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) we prove that the addressed problem is NP-Hard; (ii) a fast heuristic and an exponential-time exact algorithm are described; (iii) a wide experimental analysis is performed to show the effectiveness of our techniques. [Copyright &y& Elsevier]

Abstract: In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of horizontal lines and each edge of G is drawn as a polyline containing at most bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each , there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is -hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar. [Copyright &y& Elsevier]