Concept

Planarity testing

Related publications (40)

Segmenting Planar Superpixel Adjacency Graphs w.r.t. Non-planar Superpixel Affinity Graphs

We address the problem of segmenting an image into a previously unknown number of segments from the perspective of graph partitioning. Specifically, we consider minimum multicuts of superpixel affinity graphs in which all affinities between non-adjacent su ...

2013

Design and fabrication of a novel centimeter scale three dimensional silicon tip, tilt and piston mirror mechanism

François Barrot, Dara Zaman Bayat, Johannes Richard Cornelis Geerit Kruis, Rémy Fournier

A novel centimetre scale tip tilt piston mirror mechanism has been designed in silicon. The mirror consists of three identical mechanism parts and one mirror part. The fabrication of the parts was done with photolithography and Deep Reactive Ion Etching an ...

2013

Sensor and actuator integrated low-profile robotic Origami

Jamie Paik, Amir Firouzeh, Yi Sun

The robotic origami (Robogami) is a low-profile, sheet-like robot with multi degrees-of-freedom (DoF) that embeds different functional layers. Due to its planar form, it can take advantage of precise 2D fabrication methods usually reserved for micro and na ...

Ieee2013

Efficient graph planarization in sensor networks and local routing algorithm

Florian Huc

In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under ligh ...

Ieee2012

Diameter Bounds for Planar Graphs

Radoslav Fulek, Filip Moric, David Pritchard

The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method ...

Elsevier2011

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Functional Webs for Freeform Architecture

Bailin Deng

Rationalization and construction-aware design dominate the issue of realizability of freeform architecture. The former means the decomposition of an intended shape into parts which are sufficiently simple and efficient to manufacture; the latter refers to ...

Wiley-Blackwell2011

Electromagnetic Modelling of Planar Circuits Embedded in Laterally Shielded Multilayered Media

Laleh Golestanirad

Multilayered media with printed circuits embedded between their dielectric layers are one of the most successful technologies for manufacturing planar structures with a very promising performance-to-price ratio. These planar structures include many differe ...

EPFL2011

Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

Carsten Moldenhauer

NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...

Academic Press Inc Elsevier Science2011

Decomposition of Geometric Set Systems and Graphs

We study two decomposition problems in combinatorial geometry. The first part of the thesis deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold coveri ...

EPFL2010

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.