Search

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

A mixed graph has both directed and undirected edges. We study how to compute a crossing-free drawing of an embedded planar mixed graph, such that it is upward 'as much as possible'. Roughly speaking, in an upward drawing of a mixed graph all (undirected) edges are monotone in the vertical direction and directed edges flow monotonically from bottom to top according to their orientation. We study quasi-upward drawings of mixed graphs, that is, upward drawings where edges can break the vertical monotonicity in a finite number of edge points, called bends. We describe both efficient heuristic techniques and exact approaches for computing quasi-upward planar drawings of embedded mixed graphs with few bends, and we extensively compare them experimentally: the results suggest that our algorithms are effective in many cases. [ABSTRACT FROM AUTHOR]

A simultaneous geometric embedding (SGE) of two planar graphs G1 and G2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G1 and Γ2 of G2 such that each vertex is drawn at the same point in Γ1 Γ2. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where Γ1 and Γ2 are required to be quasi-planar (i.e. they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up several new interesting research questions. [ABSTRACT FROM AUTHOR]

A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is $\mathcal{NP}$-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings. [ABSTRACT FROM AUTHOR]

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: In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. [Copyright &y& Elsevier]