Search

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term "robust" to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures. We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in k -dimensional spaces and related problems, SIAM J. Comput.11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput.28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput.29(5) (2000) 1401–1421). As a side effect of our results, we solve a question left open by Katajainen27 (J. Katajainen, The region approach for computing relative neighborhood graphs in the L p metric, Computing40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points S in the plane under the L 2 metric. [ABSTRACT FROM AUTHOR]

This paper deals with the fast computation of straight skeletons of planar straight-line graphs (PSLGs) at an industrial-strength level. We discuss both the theoretical foun-dations of our algorithm and the engineering aspects of our implementation BONE. Our investigation starts with an analysis of the triangulation-based algorithm by Aichholzer and Aurenhammer and we prove the existence of flip-event-free Steiner triangulations. This result motivates a careful generalization of motorcycle graphs such that their inti-mate geometric connection to straight skeletons is maintained. Based on the generalized motorcycle graph, we devise a non-procedural characterization of straight skeletons of PSLGs and we discuss how to obtain a discretized version of a straight skeleton by means of graphics rendering. Most importantly, this generalization allows us to present a fast and easy-to-implement straight-skeleton algorithm. We implemented our algorithm in C++ based on floating-point arithmetic. Extensive benchmarks with our code BONE demonstrate an 0(n log N) time complexity and 0(n) memory footprint on 22 300 datasets of diverse characteristics. This is a linear factor better than the implementation provided by CGAL 4.0, which shows an 0(n² logn) time complexity and an 0(n²) memory footprint; the CGAL code has been the only fully-functional straight-skeleton code so far. In particular, on datasets with ten thousand vertices, BONE requires about 0.2-0.6 seconds instead of 4-7 minutes consumed by the CGAL code, and BONE uses only 20 MB heap memory instead of several gigabytes. We conclude our paper with a discussion of the engineering aspects and principles that make BONE reliable enough to compute the straight skeleton of datasets comprising a few million vertices on a desktop computer. [ABSTRACT FROM AUTHOR]

In this paper we consider the ip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs.We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs is connected and has diameter O( n2), even in the case of labeled vertices with fixed outer face. For this case we provide an Ω(n log n) lower bound. [ABSTRACT FROM AUTHOR]

In this paper, we study the point-set embeddability problem, i.e., given a planar graph and a set of points, is there a mapping of the vertices to the points such that the resulting straight-line drawing is planar? It was known that this problem is NP-hard if the embedding can be chosen, but becomes polynomial for triangulated graphs of treewidth 3. We show here that in fact it can be answered for all planar graphs with a fixed combinatorial embedding that have constant treewidth and constant face-degree. We prove that as soon as one of the conditions is dropped (i.e., either the treewidth is unbounded or some faces have large degrees), point-set embeddability with a fixed embedding becomes NP-hard. The NP-hardness holds even for a 3-connected planar graph with constant treewidth, triangulated planar graphs, or 2-connected outer-planar graphs. These results also show that the convex point-set embeddability problem (where faces must be convex) is NP-hard, but we prove that it becomes polynomial if the graph has bounded treewidth and bounded maximum degree. [ABSTRACT FROM AUTHOR]

There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of 'right angle crossing (RAC)' drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of 'outer-1-plane' graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. [ABSTRACT FROM AUTHOR]

The problem of deciding the unique realizability of a graph in a Euclidean space with distance and/or direction constraints on the edges of the graph has applications in CAD (Computer-Aided Design) and localization in sensor networks. One approach, which has been proved to be efficient in the similar problem for graphs with distance constraints, is to study operations to construct a uniquely realizable graph from a smaller one. In this paper, we extend a result of Jackson and Jordán on the unique realizability preservingness of the so-called '1-extension' in dimension 2 to all dimensions. [ABSTRACT FROM AUTHOR]

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters. [ABSTRACT FROM AUTHOR]

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L1 plane has a lower bound of Ω(n n) in the algebraic computation tree model and describe a worst-case O(σn 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ ≥ 2 vectors and a worst-case O(n d n) time algorithm to d ≥ 3 dimensions in L1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L1 plane. [ABSTRACT FROM AUTHOR]

Stoker's theorem states that in a convex polyhedron, the dihedral angles and edge lengths determine the facial angles if the graph is fixed. In this paper, we study under what conditions Stoker's theorem holds for orthogonal polyhedra, obtaining uniqueness and a linear-time algorithm in some cases, and NP-hardness in others. [ABSTRACT FROM AUTHOR]

Given a set T of n points in ℝ2, a Manhattan network on T is a graph G = (V,E) with the property that all the edges in E are vertical or horizontal line segments connecting points in V ⊇ T and for all p, q ∈ T, the graph contains a path having the length exactly L1 distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments of the network. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves over a recent combinatorial 2-approximation algorithm with running time O(n2). Moreover, compared with other 2-approximation algorithms using linear programming or dynamic programming techniques, we show that a greedy strategy suffices to obtain a 2-approximation algorithm. [ABSTRACT FROM AUTHOR]

It has been shown that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ(n2) area. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree (directed trees), is a bipartite graph (directed bipartite graphs), or is an outerplanar graph (directed outerplanar graphs). Concerning directed trees, we show that optimal Θ(n log n) area upward straight-line/poly-line planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs. [ABSTRACT FROM AUTHOR]

Let G1 and G2 be two planar graphs having some vertices in common. A simultaneous embedding of G1 and G2 is a pair of crossing-free drawings of G1 and G2 such that each vertex in common is represented by the same point in both drawings. In this paper we show that an outerplanar graph and a simple path can be simultaneously embedded with fixed edges such that the edges in common are straight-line segments while the other edges of the outerplanar graph can have at most one bend per edge. We then exploit the technique for outerplanar graphs and paths to study simultaneous embeddings of other pairs of graphs. Namely, we study simultaneous embedding with fixed edges of: (i) two outerplanar graphs sharing a forest of paths and (ii) an outerplanar graph and a cycle. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space ℝd (for any constant integer d ≥ 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the δ-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in ℝd. In particular, our approximation algorithm based on the ∊-fuzzy distance function takes O(n log n) time for any given fixed value ∊>0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets. [ABSTRACT FROM AUTHOR]

In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. [ABSTRACT FROM AUTHOR]

In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study orthogonal drawing algorithms that work for any input graph, and discuss different models for such drawings. Then we introduce the three-phase method, a generic technique to create high-degree orthogonal drawings. This approach simplifies the description and implementation of orthogonal graph drawing, and can be applied to global as well as interactive and incremental settings. [ABSTRACT FROM AUTHOR]

In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice. [ABSTRACT FROM AUTHOR]

In general, visibility reconstruction problems involve determining a set of objects in the plane that exhibit a specified set of visibility constraints. In this paper, an algorithm is presented for reconstructing a set of parallel line segments from specified visibility information contained in an extended endpoint visibility graph. The algorithm runs in polynomial time and relies on simple vector arithmetic to generate a system of linear inequalities. A related problem, solvable with the same technique, is the point reconstruction problem, in which the cyclic ordering and the x-coordinates of a set of points is specified. A second contribution is the definition of an extension of the visibility graph called the Stab Graph, which contains extra visibility information. [ABSTRACT FROM AUTHOR]