Publication

Decomposition of Geometric Set Systems and Graphs

Publications associées (35)

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

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

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

On the connectivity of visibility graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibil ...

2011

On the Page Number of Upward Planar Directed Acyclic Graphs

Radoslav Fulek, Fabrizio Frati, Andres Jacinto Ruiz Vargas

In this paper we study the page number of upward planar directed acyclic graphs. We prove that: (I) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min {O(k log n), O(2(k) ...

Springer-Verlag Berlin2011

Convex polygons are cover-decomposable

We show that for any open convex polygon P, there is a constant k(P) such that any k(P)-fold covering of the plane with translates of P can be decomposed into two coverings. ...

2010

Indecomposable Coverings with Concave Polygons

We show that for any concave polygon that has no parallel sides and for any k, there is a k-fold covering of some point set by the translates of this polygon that cannot be decomposed into two coverings. Moreover, we give a complete classification of open ...

Springer-Verlag2010

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Perfect Simulation and Stationarity of a Class of Mobility Models

Jean-Yves Le Boudec, Milan Vojnovic

We define ``random trip", a generic mobility model for independent mobiles that contains as special cases: the random waypoint on convex or non convex domains, random walk with reflection or wrapping, city section, space graph and other models. We use Palm ...

2005

Perfect Simulation and Stationarity of a Class of Mobility Models

Jean-Yves Le Boudec, Milan Vojnovic

2004