An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.

Property Value
dbo:abstract
  • En teoría de grafos, el espesor (o también grosor) de un grafo G es el número mínimo de grafos planos en el que se pueden dividir las aristas de G. Es decir, si existe una colección de grafos planos k, todos con el mismo conjunto de vértices, tal que la unión de estos grafos planos es G, entonces el grosor de G es como máximo k.​​ En otras palabras, el espesor de un grafo es el número mínimo de planos subgrafos cuya unión es igual al grafo G.​ Así, un grafo plano tiene espesor 1. Los grafos de espesor 2 se denominan grafos biplanares. El concepto de espesor se origina en la conjetura planteada por en 1962: cualquier grafo de 9 puntos, ya sea él mismo o su grafo complemento, es no-plano. El problema es equivalente a determinar si el grafo completo K9 es biplanar (no lo es, y la conjetura es verdadera).​​ , Thomas Odenthal y Mark Scharbrodt escribieron una recopilación exhaustiva sobre el estado del arte del tema en 1998.​ (es)
  • In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G. Thus, a planar graph has thickness 1. Graphs of thickness 2 are called biplanar graphs. The concept of thickness originates in the 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary graph is non-planar. The problem is equivalent to determining whether the complete graph K9 is biplanar (it is not, and the conjecture is true). A comprehensive survey on the state of the arts of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal and Mark Scharbrodt. (en)
  • У теорії графів товщина графа G — це найменша кількість плоских підграфів, на які можна розкласти ребра графа G. Тобто, якщо існує набір k плоских графів, які мають однаковий набір вершин, поєднання яких дає граф G, то товщина графа G не більше k. Таким чином, плоский граф має товщину 1. Графи з товщиною 2 називають двопланарними графами. Концепція товщини виникла в гіпотезі Френка Харарі 1962 року: будь-який граф з 9 вершинами або сам, або його доповнення, є непланарним. Задача еквівалентна визначенню, чи є повний граф K9 біпланарним (він не біпланарний, так що гіпотеза істинна). Всебічний огляд з теми товщини графа (станом на 1998 рік) написали Мутцель, Оденталь і Шарбродт. (uk)
  • В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k. Таким образом, плоский граф имеет толщину 1. Графы с толщиной 2 называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф K9 бипланарным (он не бипланарен, так что гипотеза верна). Всесторонний обзор по теме толщины графа (по состоянию на 1998 год) написан Мутцелем, Оденталем и Шарбродтом. (ru)
dbo:wikiPageID
  • 43082178 (xsd:integer)
dbo:wikiPageLength
  • 8143 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1113783606 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdfs:comment
  • En teoría de grafos, el espesor (o también grosor) de un grafo G es el número mínimo de grafos planos en el que se pueden dividir las aristas de G. Es decir, si existe una colección de grafos planos k, todos con el mismo conjunto de vértices, tal que la unión de estos grafos planos es G, entonces el grosor de G es como máximo k.​​ En otras palabras, el espesor de un grafo es el número mínimo de planos subgrafos cuya unión es igual al grafo G.​ (es)
  • In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G. (en)
  • В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k. (ru)
  • У теорії графів товщина графа G — це найменша кількість плоских підграфів, на які можна розкласти ребра графа G. Тобто, якщо існує набір k плоских графів, які мають однаковий набір вершин, поєднання яких дає граф G, то товщина графа G не більше k. (uk)
rdfs:label
  • Espesor (teoría de grafos) (es)
  • Толщина графа (ru)
  • Thickness (graph theory) (en)
  • Товщина графа (uk)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License