SPQR tree
http://dbpedia.org/resource/SPQR_tree an entity of type: Abstraction100002137
In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in and graph drawing.
rdf:langString
En théorie des graphes, un arbre SPQR est une structure de données arborescente utilisée en informatique, et plus spécifiquement en algorithmique de graphes, pour représenter les composantes triconnexes d'un graphe. L'arbre SPQR d'un graphe peut être construit en temps linéaire ; plusieurs applications dans les algorithmes de graphes dynamiques et dans le tracé de graphes utilisent cette structure de données.
rdf:langString
SPQR-дерево — это древесная структура данных, используемая в информатике, а именно, в алгоритмах на графах, для представления трёхсвязных компонент графа. Трёхсвязные компоненты двусвязного графа — это система более мелких графов, описывающих все 2-вершинные сечения графа. SPQR-дерево графа может быть построено за линейное время и имеет некоторые приложения в алгоритмах динамических графов и визуализации графов.
rdf:langString
rdf:langString
Arbre SPQR
rdf:langString
SPQR tree
rdf:langString
SPQR-дерево
xsd:integer
11220797
xsd:integer
1097624605
rdf:langString
Saunders Mac Lane
rdf:langString
Saunders
rdf:langString
Mac Lane
rdf:langString
Di Battista
rdf:langString
Tamassia
xsd:integer
1937
1989
1990
1996
rdf:langString
In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in and graph drawing. The basic structures underlying the SPQR tree, the triconnected components of a graph, and the connection between this decomposition and the planar embeddings of a planar graph, were first investigated by Saunders Mac Lane; these structures were used in efficient algorithms by several other researchers prior to their formalization as the SPQR tree by Di Battista and Tamassia .
rdf:langString
En théorie des graphes, un arbre SPQR est une structure de données arborescente utilisée en informatique, et plus spécifiquement en algorithmique de graphes, pour représenter les composantes triconnexes d'un graphe. L'arbre SPQR d'un graphe peut être construit en temps linéaire ; plusieurs applications dans les algorithmes de graphes dynamiques et dans le tracé de graphes utilisent cette structure de données. Les structures de base sous-jacentes à unarbre SPQR, sont les composantes triconnexes d'un graphe et la relation entre cette décomposition et les plongements planaires d'un graphe planaire; ces relations ont d'abord été étudiés par Saunders Mac Lane ; ces structures ont été utilisées dans des algorithmes efficaces par plusieurs autres chercheurs avant leur formalisation en termes d'arbre SPQR par Di Battista et Tamassia.
rdf:langString
SPQR-дерево — это древесная структура данных, используемая в информатике, а именно, в алгоритмах на графах, для представления трёхсвязных компонент графа. Трёхсвязные компоненты двусвязного графа — это система более мелких графов, описывающих все 2-вершинные сечения графа. SPQR-дерево графа может быть построено за линейное время и имеет некоторые приложения в алгоритмах динамических графов и визуализации графов. Базовую структуру, лежащую в основе SPQR-дерева — трёхсвязные компоненты графа, и связь между таким разложением и планарными вложениями первым изучал Маклейн. Эти структуры другие исследователи использовали в эффективных алгоритмах до их формализации как SPQR-дерево Ди Батистой и Тамассиа.
xsd:nonNegativeInteger
13460
