SPQR tree (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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 . (en) 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. (fr) SPQR-дерево — это древесная структура данных, используемая в информатике, а именно, в алгоритмах на графах, для представления трёхсвязных компонент графа. Трёхсвязные компоненты двусвязного графа — это система более мелких графов, описывающих все 2-вершинные сечения графа. SPQR-дерево графа может быть построено за линейное время и имеет некоторые приложения в алгоритмах динамических графов и визуализации графов. Базовую структуру, лежащую в основе SPQR-дерева — трёхсвязные компоненты графа, и связь между таким разложением и планарными вложениями первым изучал Маклейн. Эти структуры другие исследователи использовали в эффективных алгоритмах до их формализации как SPQR-дерево Ди Батистой и Тамассиа. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/SPQR_tree_2.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.ogdf.uni-osnabrueck.de/doc/_s_p_q_r_tree_8h_source.html http://code.google.com/p/jbpt/ http://cs.brown.edu/research/pubs/pdfs/1996/DiBattista-1996-OPT.pdf |
| dbo:wikiPageID | 11220797 (xsd:integer) |
| dbo:wikiPageLength | 13460 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097624605 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbr:Multigraph dbr:Biconnected_component dbc:Graph_connectivity dbr:Permutation dbr:Undirected_graph dbr:Depth-first_search dbr:Orientation_(graph_theory) dbr:Clique-sum dbr:Gomory–Hu_tree dbr:Tree_data_structure dbr:Linear_time dbr:Stack_(abstract_data_type) dbr:Computer_science dbr:Tree_(graph_theory) dbr:Tree_decomposition dbr:Lecture_Notes_in_Computer_Science dbr:Trémaux_tree dbr:Cycle_graph dbr:Dual_graph dbr:Graph_drawing dbr:Graph_theory dbc:Graph_data_structures dbc:Trees_(data_structures) dbr:Biconnected_graph dbr:Dipole_graph dbr:Planar_graph dbr:Graph_algorithm dbr:Bucket_sort dbr:Orientability dbr:Radix_sort dbr:Series–parallel_graph dbr:Dynamic_graph_algorithm dbr:File:SPQR_tree_2.svg |
| dbp:authorlink | Saunders Mac Lane (en) |
| dbp:first | Saunders (en) |
| dbp:last | Mac Lane (en) Di Battista (en) Tamassia (en) |
| dbp:wikiPageUsesTemplate | dbt:CS-Trees dbt:Citation dbt:Harvtxt dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Harvs |
| dbp:year | 1937 (xsd:integer) 1989 (xsd:integer) 1990 (xsd:integer) 1996 (xsd:integer) |
| dct:subject | dbc:Graph_connectivity dbc:Graph_data_structures dbc:Trees_(data_structures) |
| gold:hypernym | dbr:System |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:WikicatGraphDataStructures yago:Structure105726345 |
| rdfs:comment | 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. (en) 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. (fr) SPQR-дерево — это древесная структура данных, используемая в информатике, а именно, в алгоритмах на графах, для представления трёхсвязных компонент графа. Трёхсвязные компоненты двусвязного графа — это система более мелких графов, описывающих все 2-вершинные сечения графа. SPQR-дерево графа может быть построено за линейное время и имеет некоторые приложения в алгоритмах динамических графов и визуализации графов. (ru) |
| rdfs:label | Arbre SPQR (fr) SPQR tree (en) SPQR-дерево (ru) |
| owl:sameAs | freebase:SPQR tree yago-res:SPQR tree wikidata:SPQR tree dbpedia-fa:SPQR tree dbpedia-fr:SPQR tree dbpedia-ru:SPQR tree dbpedia-sr:SPQR tree https://global.dbpedia.org/id/2h3FJ |
| prov:wasDerivedFrom | wikipedia-en:SPQR_tree?oldid=1097624605&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/SPQR_tree_2.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:SPQR_tree |
| is dbo:wikiPageDisambiguates of | dbr:SPQR_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:SPQR-tree dbr:Triconnected_component dbr:Spqr_decomposition |
| is dbo:wikiPageWikiLink of | dbr:Saunders_Mac_Lane dbr:Petra_Mutzel dbr:Mac_Lane's_planarity_criterion dbr:SPQR-tree dbr:Book_embedding dbr:List_of_graph_theory_topics dbr:1-planar_graph dbr:Clique-sum dbr:Apex_graph dbr:Feedback_arc_set dbr:Brigitte_Servatius dbr:Dual_graph dbr:SPQR_(disambiguation) dbr:Series–parallel_graph dbr:Triconnected_component dbr:Spqr_decomposition |
| is foaf:primaryTopic of | wikipedia-en:SPQR_tree |
