Boxicity (original) (raw)
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices. (en) En teoría de grafos, la cajeidad (boxicity en inglés) es un , introducido por en 1969. La cajeidad de un grafo es la dimensión mínima en la que un grafo dado puede representarse como un grafo de intersección de cajas paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los vértices del grafo y un conjunto de cajas, tal que dos cajas se intersecan si y solo si hay una arista en el grafo que conecta los vértices correspondientes. (es) В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969. Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины. (ru) У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році. Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Boxicity.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p51 https://web.archive.org/web/20170830050212/http:/www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf http://portal.acm.org/citation.cfm%3Fid=1070470 |
| dbo:wikiPageID | 11167471 (xsd:integer) |
| dbo:wikiPageLength | 13579 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097177735 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Degeneracy_(graph_theory) dbr:Perfect_matching dbr:Vertex_cover dbr:Degree_(graph_theory) dbc:Graph_invariants dbr:Complete_graph dbr:Graph_minor dbc:Geometric_graph_theory dbr:NP-complete dbr:Logarithm dbr:Comparability_graph dbr:Computational_Geometry_(journal) dbr:Outerplanar_graph dbr:Partially_ordered_set dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Order_dimension dbr:Intersection_graph dbr:Interval_graph dbr:Hypercube dbr:Bipartite_graph dbr:Colin_de_Verdière_graph_invariant dbr:Dimension dbr:Planar_graph dbr:Fred_S._Roberts dbr:Graph_invariant dbr:Maximum_clique_problem dbr:Series_B dbr:Vertex_(graph_theory) dbr:Parameterized_complexity dbr:Turán_graph dbr:Box_(shape) dbr:Cubicity dbr:File:Boxicity.svg dbr:Sphericity_(graph_theory) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_invariants dbc:Geometric_graph_theory |
| gold:hypernym | dbr:Invariant |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment | In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices. (en) En teoría de grafos, la cajeidad (boxicity en inglés) es un , introducido por en 1969. La cajeidad de un grafo es la dimensión mínima en la que un grafo dado puede representarse como un grafo de intersección de cajas paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los vértices del grafo y un conjunto de cajas, tal que dos cajas se intersecan si y solo si hay una arista en el grafo que conecta los vértices correspondientes. (es) В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969. Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины. (ru) У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році. Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини. (uk) |
| rdfs:label | Cajeidad (es) Boxicity (en) Интервальная размерность графа (ru) Інтервальна розмірність графа (uk) |
| owl:sameAs | freebase:Boxicity yago-res:Boxicity wikidata:Boxicity dbpedia-es:Boxicity dbpedia-hu:Boxicity dbpedia-ru:Boxicity dbpedia-tr:Boxicity dbpedia-uk:Boxicity https://global.dbpedia.org/id/4ajZJ |
| prov:wasDerivedFrom | wikipedia-en:Boxicity?oldid=1097177735&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Boxicity.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Boxicity |
| is dbo:wikiPageWikiLink of | dbr:Pathwidth dbr:Intersection_number_(graph_theory) dbr:Clique_problem dbr:Outerplanar_graph dbr:Graph_property dbr:Intersection_graph dbr:Interval_graph dbr:Block_graph dbr:Fred_S._Roberts dbr:Implicit_graph dbr:Χ-bounded dbr:Turán_graph |
| is foaf:primaryTopic of | wikipedia-en:Boxicity |
