Search

We demonstrate theoretically and experimentally a new electromagnetic lensing concept using the magnetic vector potential - in a region free of classical electromagnetic fields - via the Aharonov-Bohm effect. This toroid-shaped lens with poloidal current flow allows for electromagnetic lensing which can be tuned to be convex or concave with a spherical aberration coefficient of opposite polarity to its focal length. This new lens combines the advantages of traditional electromagnetic and electrostatic field-based lenses and opens up new possibilities for the optical design of charged-particle systems. More generally, these results demonstrate that the Aharonov-Bohm effect can shape charged particle wavefronts beyond simple step shifts if topologies beyond simple flux lines are considered and supports the physical significance of the magnetic vector potential., Comment: 15 pages main text (3 figures) + 16 pages supplemental (5 figures). V2: Revised flow and clarity of text

Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that describes such drawings combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. We generalize this idea to ortho-radial representations of ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. Unlike the orthogonal case, there exist ortho-radial representations that do not admit a corresponding drawing, for example so-called strictly monotone cycles. An ortho-radial drawing is called valid if it does not contain a strictly monotone cycle. Our first result is that an ortho-radial representation admits a corresponding drawing if and only if it is valid. Previously such a characterization was only known for ortho-radial drawings of paths, cycles, and theta graphs, and in the special case of rectangular drawings of cubic graphs, where the contour of each face is required to be a rectangle. Further, we give a quadratic-time algorithm that tests for an ortho-radial representation whether it is valid, and we show how to draw a valid ortho-radial representation in the same running time. Altogether, this reduces the problem of computing a minimum-bend ortho-radial drawing to the task of computing a valid ortho-radial representation with the minimum number of bends, and hence establishes an ortho-radial analogue of the topology-shape-metrics framework for planar orthogonal drawings by Tamassia., Comment: submitted to the journal Discrete & Computational Geometry. arXiv admin note: text overlap with arXiv:1903.05048

In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP). We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [14]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP. A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to approximately one and a half minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning., Comment: A preliminary version of this work was published in the Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19). This work became part of the dissertation of the first author

Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. [2] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time., Comment: 27 pages; SoCG 2019 (to appear)

SModelS is an automatised tool enabling the fast interpretation of simplified model results from the LHC within any model of new physics respecting a $\mathbb{Z}_2$ symmetry. With the version 1.2 we announce several new features. First, previous versions were restricted to missing energy signatures and assumed prompt decays within each decay chain. SModelS v1.2 considers the lifetime of each $\mathbb{Z}_2$-odd particle and appropriately takes into account missing energy, heavy stable charge particle and R-hadron signatures. Second, the current version allows for a combination of signal regions in efficiency map results whenever a covariance matrix is available from the experiment. This is an important step towards fully exploiting the constraining power of efficiency map results. Several other improvements increase the user-friendliness, such as the use of wildcards in the selection of experimental results, and a faster database which can be given as a URL. Finally, smodelsTools provides an interactive plots maker to conveniently visualize the results of a model scan., Comment: 24 pages, 4 figures

Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings., Comment: Extended version of a paper to appear at the 33rd International Symposium on Computational Geometry (SoCG 2017)

One of the most fundamental problems in wireless networks is to achieve high throughput. Fractional Connected Dominating Set (FCDS) Packings can achieve a throughput of ${\Theta}(k/\log n)$ messages for networks with node connectivity $k$, which is optimal regarding routing-based message transmission. FCDS were proposed by Censor-Hillel \emph{et al.} [SODA'14,PODC'14] and are a natural generalization to Connected Dominating Sets (CDS), allowing each node to participate with a fraction of its weight in multiple FCDS. Thus, $\Omega(k)$ co-existing transmission backbones are established, taking full advantage of the networks connectivity. We propose a modified distributed algorithm that improves upon previous algorithms for $k\Delta \in o(\min\{\frac{n \log n}{k} ,D,\sqrt{n \log n} \log^* n\}\log n)$, where $\Delta$ is the maximum node degree, $D$ the diameter and $n$ the number of nodes in the network. We achieve this by explicitly computing connections between tentative dominating sets.