Search

Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α -ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 2 π / 3 (however, our approximation ratios hold for any α ⩾ 2 π / 3 ). The α -minimum spanning tree problem asks for an α -ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α -ST of length at most 6 times the length of the minimum spanning tree (MST). By adapting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. To examine what is possible with non-uniform wedge angles, we define an α ¯ -ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α . We present an algorithm to find an α ¯ -ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α . Our algorithm runs in linear time after computing the MST. [ABSTRACT FROM AUTHOR]

We would like to thank the authors for contributing their manuscripts, the referees for thoroughly reviewing these articles and the WADS 2021 program committee for helping with the selection of these articles. This special issue is dedicated to selected papers from those presented at the 17th Algorithms and Data Structures Symposium (WADS 2021), which was held from August 9-11 fully online. [Extracted from the article]

Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with O (n 8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O (n 7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture. [ABSTRACT FROM AUTHOR]

We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. In "How to morph planar graph drawings" (SIAM Journal on Computing) the authors give a morph that consists of O(n) steps where each step is a linear morph that moves each of the n vertices in a straight line at uniform speed. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in O(n2) linear morphing steps and improve the grid size to O(n)×O(n) for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic "flip" operations of Schnyder woods as linear morphs. [ABSTRACT FROM AUTHOR]

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittability in linear time, for a constant k. [ABSTRACT FROM AUTHOR]

There are two known ways to unfold a convex polyhedron without overlap: the star unfolding and the source unfolding, both of which use shortest paths from vertices to a source point on the surface of the polyhedron. Non-overlap of the source unfolding is straightforward; non-overlap of the star unfolding was proved by Aronov and O'Rourke (Discrete Comput Geom 8(3):219-250, 1992). Our first contribution is a simpler proof of non-overlap of the star unfolding. Both the source and star unfolding can be generalized to use a simple geodesic curve instead of a source point. The star unfolding from a geodesic curve cuts the geodesic curve and a shortest path from each vertex to the geodesic curve. Demaine and Lubiw conjectured that the star unfolding from a geodesic curve does not overlap. We prove a special case of the conjecture. Our special case includes the previously known case of unfolding from a geodesic loop. For the general case we prove that the star unfolding from a geodesic curve can be separated into at most two non-overlapping pieces. [ABSTRACT FROM AUTHOR]

For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k 'walls', represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons. [ABSTRACT FROM AUTHOR]

Let σ be a directed cycle whose edges have each been assigned a desired direction in 3 D (East, West, North, South, Up, or Down) but no length. We say that σ is a shape cycle. We consider the following problem. Does there exist an orthogonal representation Γ of σ in 3 D space such that no two edges of Γ intersect except at common endpoints and such that each edge of Γ has the direction specified in σ? If the answer is positive, we say that σ is simple. This problem arises in the context of extending orthogonal graph drawing techniques from 2 D to 3 D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms. [ABSTRACT FROM AUTHOR]

We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding polytopes to polygons. Our answers are, roughly: exponentially many, or nondenumerably infinite. [ABSTRACT FROM AUTHOR]