Search

We study biplane graphs drawn on a finite planar point set $$S$$ in general position. This is the family of geometric graphs whose vertex set is $$S$$ and can be decomposed into two plane graphs. We show that two maximal biplane graphs-in the sense that no edge can be added while staying biplane-may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over $$n$$ -element point sets. [ABSTRACT FROM AUTHOR]

We study biplane graphs drawn on a finite point set $$S$$ in the plane in general position. This is the family of geometric graphs whose vertex set is $$S$$ and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges. [ABSTRACT FROM AUTHOR]

We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard. [ABSTRACT FROM AUTHOR]

Abstract: We prove that every finite set of homothetic copies of a given convex body in the plane can be colored with four colors so that any point covered by at least two copies is covered by two copies with distinct colors. This generalizes a previous result from Smorodinsky (SIAM J. Disc. Math. 2007). Then we show that for any , every three-dimensional hypergraph can be colored with colors so that every hyperedge e contains vertices with mutually distinct colors. This refines a previous result from Aloupis et al. (Disc. & Comp. Geom. 2009). As corollaries, we improve on previous results for conflict-free coloring, k-strong conflict-free coloring, and choosability. Proofs of the upper bounds are constructive and yield simple, polynomial-time algorithms. [Copyright &y& Elsevier]

Abstract We introduce the family of k-gap-planar graphs for k ≥ 0 , i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k -gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k -gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k -gap-planar complete graphs, and the computational complexity of recognizing k -gap-planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we show that the θ-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones. [Copyright &y& Elsevier]

A constant-work-space algorithm has read-only access to an input array and may use only O ( 1 ) additional words of O ( log n ) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O ( n 2 ) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O ( n 2 / s ) time. [ABSTRACT FROM AUTHOR]

Abstract: A constant-work-space algorithm has read-only access to an input array and may use only additional words of bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in time. [Copyright &y& Elsevier]

Abstract: Given a set S of points in the plane representing wireless devices, each point equipped with a directional antenna of radius r and aperture angle , our goal is to find orientations and a minimum r for these antennas such that the induced communication graph is strongly connected. We show that if , if , if , and if suffices to establish strong connectivity, assuming that the longest edge in the Euclidean minimum spanning tree of S is 1. These results are worst-case optimal and match the lower bounds presented in [I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, A. Wiese, Communication in wireless networks with directional antennae, in: Proc. of the 20th Symp. on Parallelism in Algorithms and Architectures, 2008, pp. 344–351]. In contrast, is sometimes necessary when . [Copyright &y& Elsevier]

Abstract: We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, connectivity, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross. [Copyright &y& Elsevier]