Search

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

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]

We give new results about the relationship between 1-planar graphs and RAC graphs . A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs , the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar. [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: 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: 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]

A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other partition, together with the edges, must be added to the drawing without any restriction on their positions. We assume that G is planar and study the problem of finding a planar straight-line drawing of G. We show that deciding whether G admits such a drawing is NP -hard in the general case. Under the assumption that each mobile vertex is placed in the convex hull of its neighbors, we are able to prove that the problem is also in NP. Moreover, if the intersection graph of these convex hulls is a path, a cycle or, more generally, a cactus, the problem is polynomial-time solvable through a dynamic programming approach. Finally, we describe linear-time testing algorithms when the fixed vertices are collinear or when they lie on a finite set of horizontal levels (lines) and no edge can intersect a level except at its fixed vertex. [ABSTRACT FROM AUTHOR]

A drawing of a graph is greedy if for each ordered pair of vertices u and v , there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. From an application perspective, greedy drawings are especially relevant to support routing schemes in ad hoc wireless networks. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings , where edges are horizontal or vertical segments. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation , i.e., a plane graph with prescribed vertex angles, admits a greedy rectilinear drawing. We give a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances. [ABSTRACT FROM AUTHOR]

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt [35] , who proved that every n -vertex fan-planar drawing has at most 5 n − 10 edges, and that this bound is tight for n ≥ 20 . We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k -planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete. [ABSTRACT FROM AUTHOR]