Planarity testing

Formal sciences
Mathematics
Discrete mathematics
Graph theory

Related publications (29)

Page 2 of 2

About
Privacy
Disclaimer

Graph Chatbot

Related publications (29)

Page 2 of 2

Clustered planarity testing revisited

Radoslav Fulek, Jan Kyncl, Igor Malinovic

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generali ...

2015

Outerplanar graph drawings with few slopes

Bartosz Maria Walczak

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...

Elsevier Science Bv2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

On The Queue Number Of Planar Graphs

János Pach, Fabrizio Frati

We prove that planar graphs have O(log(2) n) queue number, thus improving upon the previous O(root n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log(8) n) volume, thus improving upon th ...

Siam Publications2013

Drawing Planar Graphs Of Bounded Degree With Few Slopes

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

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 ...

SIAM Publications2013

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

François Barrot, Johannes Richard Cornelis Geerit Kruis, Dara Zaman Bayat

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

Patient-specific mean pressure drop in the systemic arterial tree, a comparison between 1-D and 3-D models

Nikolaos Stergiopoulos, François Lazeyras, Philippe Reymond

One-dimensional models of the systemic arterial tree are useful tools for studying wave propagation phenomena, however, their formulation for frictional losses is approximate and often based on solutions for developed flow in straight non-tapered arterial ...

Elsevier2012