Planar separator theorem

Related publications (29)

About
Privacy
Disclaimer

Graph Chatbot

Realizability of planar point embeddings from angle measurements

Majed El Helou, Adam James Scholefield, Frederike Dümbgen

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor loca ...

IEEE2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Planar Point Sets Determine Many Pairwise Crossing Segments

János Pach, Gábor Tardos

We show that any set of n points in general position in the plane determines n(1-o(1)) pairwise crossing segments. The best previously known lower bound, Omega(root n), was proved more than 25 years ago by Aronov, Erdos, Goddard, Kreitman, Krugerman, Pach, ...

ASSOC COMPUTING MACHINERY2019

Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces

Corentin Jean Dominique Fivet, Pierluigi D'Acunto

This article develops a vector-based 3D graphic statics framework that uses synthetic and intuitive graphical means for the analysis and design of spatial structures such as networks of bar elements in static equilibrium. It is intended to support the coll ...

2019

Dual-Band Circularly Polarized Transmitarray Antenna for Satellite Communications at (20 to 30) GHz

Juan Ramon Mosig, Maria Garcia Vigueras, Joana Rita Alves dos Santos Silva, Santiago Capdevila Cascante, Hamed Hasani

A novel dual-band polarization-independent transmitarray is introduced in this paper for communication systems in Ka-band. Thanks to its unit-cell topology, the transmitarray antenna demonstrates almost complete independent performance at two design freque ...

2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

High-performance normally-off tri-gate GaN power MOSFETs

Elison de Nazareth Matioli, Jun Ma, Luca Nela, Minghua Zhu

In this work, we present the investigation of the combination of gate recess and tri-gate structures to achieve high performance normally-off GaN-on-Si MOSFETs with high positive threshold voltage ( VTH ), low specific on resistance ( RON,SP ) and high out ...

IEEE2019

Mechanics of a pressure-controlled adhesive membrane for soft robotic gripping on curved surfaces

Jamie Paik, Sukho Song, Metin Sitti

This paper aims at understanding the adhesion mechanics of a pressure-controlled adhesive thin elastomeric membrane for soft robotic gripping on non-planar, curved surfaces. The adhesive elastic membrane is lined with gecko-inspired microfiber arrays and c ...

2019

Photoinitiator-free Laser Fabrication of Ultra-compact, Low-loss Waveguides in Polydimethylsiloxane

Demetri Psaltis, Christophe Moser, Ye Pu, Giulia Panusa, Jieping Wang

Owing to its excellent elasticity, wide spectral range of transparency, and outstanding chemical and thermal stability, polydimethylsiloxane (PDMS) is an elastomer of great technological importance, being widely used in the fabrication of microfluidic and ...

SPIE-INT SOC OPTICAL ENGINEERING2018

Page 2 of 3

Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces

Corentin Jean Dominique Fivet, Pierluigi D'Acunto

2019