A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane
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.
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 ...
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 ...
We consider graphs that admit polyline drawings where all crossings occur at the same angle alpha is an element of (0, pi/2]. We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This r ...
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...
IEEE Computer Society2011
,
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions f ...
We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [xi,xj], c(xi)=c(xj) and for every arc (xp,xq), $c(x_{p})
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 ...
Multiscale representations such as the wavelet transform are useful for many signal processing tasks. Graphs are flexible models to represent complex networks and a spectral graph wavelet transform (SGWT) has recently been developed as a generalization of ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs. We show that they are both NP-complete in cubic planar bipartite graphs. This answers an open question from \cite{Ries2}. ...
We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...
