Ê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.

Graph
Search

fr|en

Se Connecter

Concept

Tracé de graphes

Résumé

En théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Types de tracés Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation. Cette représentation graphique ne doit pas être confondue avec le graphe lui-même (la structure abstraite et non graphique). Des dessins très différents peuvent correspondre au même graphe. La seule chose qui compte vraiment est le nombre d'arêtes entre chaque paire de sommets. En pratique, cependant l'arrangement de ces nœuds et arêtes influence la compréhensibilité, l'usabilité, le coût de fabrication et l'esthétique. D'

Source officielle

https://fr.wikipedia.org/wiki/Trac%C3%A9_de_graphes

À 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 (25)

Publications associées

Chargement

Personnes associées (5)

, , , ,

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (29)

Concepts associés

Chargement

Cours associés (3)

Cours associés

Chargement

Séances de cours associées (4)

Séances de cours associées

Chargement

This paper presents an unsupervised, graph based approach for extractive summarization of meetings. Graph based methods such as TextRank have been used for sentence extraction from news articles. These methods model text as a graph with sentences as nodes and edges based on word overlap. A sentence node is then ranked according to its similarity with other nodes. The spontaneous speech in meetings leads to incomplete, illformed sentences with high redundancy and calls for additional measures to extract relevant sentences. We propose an extension of the TextRank algorithm that clusters the meeting utterances and uses these clusters to construct the graph. We evaluate this method on the AMI meeting corpus and show a significant improvement over TextRank and other baseline methods.

Idiap2009

Chargement

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 represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em 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 which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016

Chargement

This paper presents an unsupervised, graph based approach for extractive summarization of meetings. Graph based methods such as TextRank have been used for sentence extraction from news articles. These methods model text as a graph with sentences as nodes and edges based on word overlap. A sentence node is then ranked according to its similarity with other nodes. The spontaneous speech in meetings leads to incomplete, informed sentences with high redundancy and calls for additional measures to extract relevant sentences. We propose an extension of the TextRank algorithm that clusters the meeting utterances and uses these clusters to construct the graph. We evaluate this method on the AM I meeting corpus and show a significant improvement over TextRank and other baseline methods.

Isca-Inst Speech Communication Assoc, C/O Emmanuelle Foxonet, 4 Rue Des Fauvettes, Lieu Dit Lous Tourils, Baixas, F-66390, France2009

Chargement

Simple topological graphs

Andres Jacinto Ruiz Vargas

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016