On the Structure of Graphs with Low Obstacle Number
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.
Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...
We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...
A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new verte ...
Embedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spat ...
A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...
Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...
This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously publish ...
We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends pe ...
Non-adaptive group testing involves grouping arbitrary subsets of n items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010
