The edge-length ratio of a planar straight-line drawing Γ of a graph G is the largest ratio between the lengths of every pair of edges of Γ. If the ratio is measured by considering only pairs of edges that are incident to a common vertex, we talk about local edge-length ratio. The (local) edge-length ratio of a planar graph is the infimum over all (local) edge-length ratios of its planar straight-line drawings. It is known that the edge-length ratio of outerplanar graphs is upper bounded by a constant, while there exist graph families with non-constant outerplanarity that have non-constant lower bounds on their edge-length ratios. In this paper we prove an Ω ( n ) lower bound on the local edge-length ratio (and hence on the edge-length ratio) of the n -vertex 2-outerplanar graphs. We also prove a constant upper bound on the edge-length ratio of Halin graphs, pseudo-Halin graphs, and their generalizations.

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.

We develop constant-factor approximation algorithms for minimizing the execution time of a coordinated parallel motion plan for a relatively dense swarm of homogeneous robots in the absence of obstacles. In our first model, each robot has a specified start and destination on the square grid, and in each round of coordinated parallel motion, every robot can move to any adjacent position that is either empty or simultaneously being vacated by another robot. In this model, our algorithm achieves constant stretch factor: if every robot starts at distance at most $d$ from its destination, then the total duration of the overall schedule is $O(d)$, which is optimal up to constant factors. Our result holds for distinguished robots (each robot has a specific destination), identical (unlabeled) robots, and most generally, classes of different robot types (where each destination specifies a required type of robot). We also show that finding the optimal coordinated parallel motion plan is NP-hard, justifying approximation algorithms. In our second model, each robot is a unit-radius disk in the plane, and robots can translate continuously in parallel subject to not intersecting, i.e., having disk centers at $L_2$-distance at least $2$. We prove the same result---constant-factor approximation algorithm to minimizing execution time via constant stretch factor---when the pairwise $L_{\infty}$-distance between disk centers is at least $2\sqrt{2}=2.8284\dots$. On the other hand, for $N$ densely packed disks at distance at most $2+\delta$ for a sufficiently small $\delta>0$, we prove that a stretch factor of $\Omega(N^{1/4})$ is sometimes necessary (when densely packed), while a stretch factor of $\mathcal{O}(N^{1/2})$ is always possible.

Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma partially preserves the topology of G if it has the same external boundary, the same rotation system, and the same set of crossings as G. Drawing Gamma fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We show that if the set of crossing-free edges of G forms a connected spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). Concerning drawings that fully preserve the topology, we show that if G has skewness k, it admits one such drawing with curve complexity at most 2k; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

A simultaneous geometric embedding (SGE) of two planar graphs |$G_1$| and |$G_2$| with the same vertex set is a pair of straight-line planar drawings |$\Gamma _1$| of |$G_1$| and |$\Gamma _2$| of |$G_2$| such that each vertex is drawn at the same point in |$\Gamma _1$| and |$\Gamma _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 |$\Gamma _1$| and |$\Gamma _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.

Given a large weighted graph G = (V, E) and a subset U of V , we define several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.

Distributing sensing and data gathering tasks to a dominating set is an attractive choice in wireless sensors networks since it helps prolong network lifetime by engaging such a subset of nodes for these tasks and letting other nodes go into energy-efficient sleep mode. Because they are busy all the time for sensing, processsing, and transmitting data, nodes in the dominating set quickly run out of energy. One possible way to overcome this situation is to find a number of dominating sets among the nodes of the network and use them one by one iteratively. In this paper, we investigate the problem of finding the maximum number of disjoint dominating sets called the domatic partition problem in unit disk graphs. Although the domatic partition problem is NP-hard in general graphs, it is unknown whether the same is true for unit disk graphs. However, we present an algorithm towards solving this problem (approximately) together with experimental results and give a conjecture based on our results about the maximum number of disjoint dominating sets in unit disk graphs.

Connected dominating sets (CDSs) are probably the most common way of constructing virtual backbones for broadcasting operation in wireless sensor networks. This is because such backbones guarantee to reduce unnecessary message transmissions or flooding in the network. In this paper we propose a simple localized algorithm to construct a small-sized CDS. Considering the sensors deployed in the plane, our main idea is based on the computation of convex hulls of sensor nodes (nodes are considered points in the plane) in a localized manner and a simple coloring scheme, which produces a CDS in unit disk graphs whose size is at most 38*|MCDS| where |MCDS| is the size of a minimum CDS. To the best of our knowledge, this is a significant improvement over the best published results in the same context [5]. We also analyze grids and trees to compute the exact approximation ratios for the problem. We show that our algorithm produces an optimal CDS if the graph is a tree and in the case of grids the approximation factor is 2.

info:eu-repo/semantics/published

introductionWe discuss properties and values of maximum matchings and minimum median problems for finite point sets.In Dar&&r.we consider "minimum stars".which are defined by a cent& chosen from the given point ' set, such that the total geometric distance min llStl[ to all the points in the set is minimized.If the center point is not required to be an element of the set (i. e., the center may be a Steiner nointj.we net a "minimum Steiner star". of total length -min I[.!?tS'tll."As a consequence of triangle inequality, the total length max IlMatll of any maximum matching is a lower bound for the length min IIStSt() of a minimum Steiner star, which makes the ratio -1 interesting in the context of optimal communication networks.The ratio also appears as the duality gap in an integer programming formulation of a location problem by Tamir and Mitchell.In this paper, we show that, for an even set of points in the plane and Euclidean distances, the ratio max,,Mat,, min llSt.Stl( ,, ,, cannot exceed 2/& This proves a conjecture of Suri, who gave an example where this bound is achieved.For the case of Euclidean distances in two and three dimensions, we also prove upper and lower bounds for the maximal value of the ratios m and z~,/~~$.We give tight upper bounds for the case where distances are measured according to the Manhattan metric: we show that in three-dimensional space, min ll.StStll max lp4atII 'Parts of this work were done while visiting Queen's University, partially supported by the Deutsche Forschungsgemeinschaft, FE 40713-l.t Parts of this work were done while visiting Universitit zu Kiiln, partially supported by NSERC.Permission to make digital or hard copies ol'all or part of this work for personal or classroom use is granted without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citalion on the tirst page.To copy otherwise, Lo

A fundamental problem in model-based computer vision is that of identifying which of a given set of geometric models is present in an image. Considering a “probe” to be an oracle that tells us whether or not a model is present at a given point, we study the problem of computing efficient strategies (“decision trees”) for probing an image, with the goal to minimize the number of probes necessary (in the worst case) to determine which single model is present. We show that a ⌈lg k ⌉ height binary decision tree always exists for k polygonal models (in fixed position), provided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an efficient algorithm for constructing such decision trees when the models are given as a set of polygons in the plane. We show that constructing a minimum height tree is NP-complete if either of the two assumptions is omitted. We provide an efficient greedy heuristic strategy and show that, in the general case, it yields a decision tree whose height is at most ⌈lg n ⌉ times that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results.

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n>

The optimal values of the parameters of the McEliece public-key cryptosystem are computed. It is shown that use of these values improves the cryptoanalytic complexity of the system and decreases its data expansion. It is shown that the likelihood of the existence of more than one trapdoor in the system is very small.>

A cryptographic scheme for controlling access to information within a group of users organized in a hierarchy was proposed in [1]. The scheme enables a user at some level to compute from his own cryptographic key the keys of the users below him in the organization.

This paper introduces four new digital signature schemes for computer communication networks. These involve one or more arbitrators who validate and authenticate messages and signatures without having access to the actual contents of the messages.