Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
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.
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 ...
Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number Θ(log log n). ...
Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...
Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...
More and more areas use graphs for the representation of their data because it gives a connection-oriented perspective. Unfortunately, datasets are constantly growing in size, while devices have increasingly smaller screens (tablets, smartphones, etc). In ...
We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...
A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-pla ...
Non-adaptive group testing involves grouping arbitrary subsets of n items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most d d ...
This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...
