Graphe d'intersection | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formally, an intersection graph G is an undirected graph formed from a family of sets by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is, Any undirected graph G may be represented as an intersection graph. For each vertex vi of G, form a set Si consisting of the edges incident to vi; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, G is the intersection graph of the sets Si. provide a construction that is more efficient, in the sense that it requires a smaller total number of elements in all of the sets Si combined. For it, the total number of set elements is at most n2/4, where n is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to , but say to see also . The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph. Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration: An interval graph is defined as the intersection graph of intervals on the real line, or of connected subgraphs of a path graph. An indifference graph may be defined as the intersection graph of unit intervals on the real line A circular arc graph is defined as the intersection graph of arcs on a circle. A polygon-circle graph is defined as the intersection of polygons with corners on a circle. One characterization of a chordal graph is as the intersection graph of connected subgraphs of a tree.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are rep

EPFL2016

Triangle-free intersection graphs of line segments with large chromatic number

Bartosz Maria Walczak, Michal Lason

In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for

Academic Press Inc Elsevier Science2014

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is prove

Springer2014

Afficher plus

Personnes associées (3)

János Pach, Bartosz Maria Walczak, Michal Lason

Concepts associés (35)

Cours associés (2)

Séances de cours associées (15)

Paramétrisation des lignes droites

Couvre la paramétrisation des lignes droites et leur interprétation géométrique.

Arbre de recherche binaire optimal

Explore les arbres de recherche binaires optimaux pour minimiser le coût de recherche attendu et discute de la représentation des graphiques à l'aide de matrices et de listes d'adjacence.

Grande expansion N: modèles vectoriels

Explore l'expansion de Large N dans les modèles vectoriels, en se concentrant sur les modèles matriciels, les théories de jauge et le couplage Hooft.

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the dat

PHYS-739: Conformal Field theory and Gravity

This course is an introduction to the non-perturbative bootstrap approach to Conformal Field Theory and to the Gauge/Gravity duality, emphasizing the fruitful interplay between these two ideas.

Graphe de disques

En théorie des graphes, un graphe de disques (ou disk graph en anglais) est le graphe d'intersection d'une collection de disques. C'est une extension du concept de graphe d'intervalle à la dimension 2. Formellement, G est un graphe de disques s'il existe une collection de disques dans le plan dont les centres sont en bijection avec les sommets de G et telle que deux disques s'intersectent si et seulement si les sommets correspondants sont reliés par une arête dans G.

Graphe d'intersection

En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite.

Circle graph

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other. gives an O(n2)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. A number of other problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs.