Search

Abstract: A (weak) closed rectangle-of-influence (RI for short) drawing is a straight-line planar grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. (1999) showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved (Biedl et al., 1999 ). Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations (Fusy, 2009 ). In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most ; and for a random irreducible triangulation, the expected grid size of the drawing is . We then prove that for arbitrary , there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size . Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in Biedl et al. (1999) negatively. [ABSTRACT FROM AUTHOR]

Abstract: Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than π). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces. These constraints are described by combinatorial pseudo-triangulations, first defined and studied in this paper. Also of interest are our two proof techniques, one based on Henneberg inductive constructions from combinatorial rigidity theory, the other on a generalization of Tutte''s barycentric embeddings to directed graphs. [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: In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of a MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min–max slope path problem in a monotone polygon which is solvable in linear time. The min–max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results. [Copyright &y& Elsevier]

Abstract: For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of Pʼs vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of Set Cover and solved in time with a greedy -approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only cells, improving the running time of the algorithm to for simple polygons. In this paper we observe that, since minimum visibility decompositions for simple polygons have only sinks (i.e., cells of minimal visibility) (Bose et al., 2000), the running time of the algorithm can be further improved to . We then extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only cells and only cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of for simple polygons and for polygons with holes. [Copyright &y& Elsevier]

Abstract: Let R be a set of red points and B a set of blue points on the plane. In this paper we introduce a new concept, which we call coarseness, for measuring how blended the elements of are. For , let be the bichromatic discrepancy of X. We say that a partition of S is convex if the convex hulls of its members are pairwise disjoint. The discrepancy of a convex partition Π of S is the minimum over the elements of Π. The coarseness of S is the discrepancy of the convex partition of S with maximum discrepancy. We study the coarseness of bicolored point sets, and relate it to well blended point sets. In particular, we show combinatorial results on the coarseness of general configurations and give efficient algorithms for computing the coarseness of two specific cases, namely when the set of points is in convex position and when the measure is restricted to convex partitions with two elements. [Copyright &y& Elsevier]

Abstract: In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community. [Copyright &y& Elsevier]

Abstract: Rectangular drawings and rectangular duals can be naturally extended to other surfaces. In this paper, we extend rectangular drawings and rectangular duals to drawings on a cylinder. The extended drawings are called rectangular-radial drawings and rectangular-radial duals. Rectangular-radial drawings correspond to periodic rectangular tilings of a 1-dimensional strip. We establish a necessary and sufficient condition for plane graphs with maximum degree 3 to have rectangular-radial drawings and a necessary and sufficient condition for triangulated plane graphs to have rectangular-radial duals. Furthermore, we present three linear time algorithms under three different conditions for finding a rectangular-radial drawing for a given cubic plane graph, if one exists. [Copyright &y& Elsevier]

Abstract: Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The algorithms we describe are (a) 2-/3-dimensional spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) d-dimensional axis-aligned box intersection computation, and finally (c) 3D bulk insertion of points into Delaunay triangulations, which can be used for mesh generation algorithms, or simply for constructing 3D Delaunay triangulations. For the latter, we introduce as a foundational element the design of a container data structure that both provides concurrent addition and removal operations and is compact in memory. This makes it especially well-suited for storing large dynamic graphs such as Delaunay triangulations. We show experimental results for these algorithms, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention. [Copyright &y& Elsevier]

Abstract: The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and it provides four algorithms based on this approach for drawing the pairs , , and . Further, it initiates the study of the matched drawability of triples of planar graphs: it presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two unlabeled level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and unlabeled level planarity. [Copyright &y& Elsevier]

Abstract: A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing. In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing. [Copyright &y& Elsevier]

Abstract: Let G be a graph with n vertices which is embedded in Euclidean space . For any two vertices of G, their dilation is defined to be the ratio of the length of a shortest connecting path in G to the Euclidean distance between them. In this paper, we study the spectrum of the dilation, over all pairs of vertices of G. For paths, cycles, and trees in , we present -time randomized algorithms that compute, for a given value , the exact number of vertex pairs of dilation at most κ. Then we present deterministic algorithms that approximate the number of vertex pairs of dilation at most κ to within a factor of . They run in time for paths and cycles, and in time for trees, in any constant dimension d. [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 the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, paths, cycles, matchings, and κ-factors for . We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of for any , where k is the number of crossings in G. We then give a simple fixed-parameter algorithm that tests in time whether G has a crossing-free configuration for any of the above, where the -notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are for spanning trees and for s-t paths and cycles. For spanning trees we also have an -time Monte-Carlo algorithm. Each -time decision algorithm can be turned into an -time optimization algorithm that computes a configuration with the minimum number of crossings. [Copyright &y& Elsevier]

In this paper, we present a linear time algorithm for constructing linkless drawings of series parallel digraphs with maximum number of symmetries. Linkless drawing in three dimensions is a natural extension to planar drawing in two dimensions. Symmetry is one of the most important aesthetic criteria in graph drawing. More specifically, we present two algorithms: a symmetry finding algorithm which finds maximum number of three dimensional symmetries, and a drawing algorithm which constructs linkless symmetric drawings of series parallel digraphs in three dimensions. [Copyright &y& Elsevier]