Concept

Test de planarité

Publications associées (40)

Note on k-planar crossing numbers

The crossing number CR(G) of a graph G = (V, E) is the smallest number of edge crossings over all drawings of G in the plane. For any k >= 1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G(0)) + CR(G(1)) + ... + CR(G(k-i)) ove ...

Elsevier Science Bv2018

On chirality of toroidal embeddings of polyhedral graphs

Senja Dominique Barthel

We investigate properties of spatial graphs on the standard torus. It is known that nontrivial embeddings of planar graphs in the torus contain a nontrivial knot or a non-split link due to [2, 3]. Building on this and using the chirality of torus knots and ...

World Scientific Publishing2017

Graph learning under sparsity priors

Pascal Frossard, Hermina Petric Maretic

Graph signals offer a very generic and natural representation for data that lives on networks or irregular structures. The actual data structure is however often unknown a priori but can sometimes be estimated from the knowledge of the application domain. ...

Ieee2017

Heuristic-driven Graph Wavelet Modeling of Complex Terrain

Alexandre Buttler, François Golay, Alexander Ludwig Johannes Peringer, Ioana Stoicescu

We present a novel method for building a multiresolution representation of large digital surface models. The surface points coincide with the nodes of a planar graph which can be processed using a critically sampled, invertible lifting scheme. To drive the ...

Spie-Int Soc Optical Engineering2015

Free Edge Lengths in Plane Graphs

Radoslav Fulek, Filip Moric

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a pla ...

Springer2015

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

Siam Publications2013

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

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

EPFL2014