About: Crossing number (graph theory)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Crossing number (graph theory) Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatInequalities, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Difference104748836 yago:Feature105849789 yago:Idea105833840 yago:Inequality104752221 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:Quality104723816 yago:WikicatGraphInvariants yago:WikicatInequalities
rdfs:label	Número de cruce (teoría de grafos) (es) Crossing number (graph theory) (en) Nombre de croisements (théorie des graphes) (fr) Минимальное число пересечений рёбер графа (ru) 交叉數 (zh) Число схрещень (uk)
rdfs:comment	在圖論，交叉數是將圖畫在平面上時，邊的交叉點的最小數目。若，則稱為平面圖。在方面，計算圖的交叉數仍是一個重要問題，因為讀者研究發現，畫圖的交叉越少，越有利於讀者理解。交叉數的研究始於。圖蘭·帕爾想求磚廠中，將每個窯爐各與全部貨倉用路軌連接的最優方案，使路軌的交叉儘可能少。按上述定義，即是問完全二部圖的交叉數。同一問題約莫同時在社會學研究提出，因為事關的繪製。圖蘭猜想了完全二部圖交叉數的公式，但該公式迄今未獲證，完全圖的交叉數公式亦然。交叉數不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。此結論在超大规模集成电路設計與組合幾何方面有應用。如無特別註明，交叉數允許使用任意曲線來畫邊。另一個相關概念是直線交叉數，其要求僅使用直線段來畫邊，所以未必等於交叉數。更具體說，完全圖的直線交叉數就是平面上處於一般位置的個點所能組成的凸四邊形的最少數目，因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與幸福結局問題密切相關。給定一個圖，計算其交叉數是一個NP難問題。 (zh) In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing. (en) En teoría de grafos, el número de cruce cr(G), también llamado número de cruzamiento, de un grafo G es el menor número de cruces de aristas en un plano del grafo G. Por ejemplo, un grafo es plano si y solo si su número de cruce es cero. (es) En théorie des graphes, le nombre de croisements cr(G) d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes. Un graphe à but informatif représenté avec peu de croisements facilite la compréhension de celui-ci. (fr) В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю. Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Km,n. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм. Задача продолжает играть большую роль в визуализации графов. (ru) В теорії графів число схрещень cr(G) графа G — це найменше число перетинів ребер плоского зображення графа G. Наприклад, граф є планарним тоді і тільки тоді, коли число його схрещень дорівнює нулю. Математичною відправною точкою вивчення числа схрещень стала задача Турана про цегельну фабрику, поставлена Палом Тураном. У цій задачі потрібно знайти число схрещень повного двочасткового графа Km,n. Однак та ж сама задача поставлена в соціології приблизно в той же самий час у зв'язку з побудовою . Задача дуже важлива для візуалізації графів. (uk)
foaf:depiction
dct:subject	Graph invariants Geometric intersection Graph drawing Topological graph theory
Wikipage page ID	18298594 (xsd:integer)
Wikipage revision ID	1109487477 (xsd:integer)
Link from a Wikipage to another Wikipage	Beck's theorem (geometry) Proportionality (mathematics) Pál Turán Quadrilaterals David S. Johnson Desargues graph Anthony Hill (artist) Approximation algorithm Richard K. Guy Cubic graph Undirected graph Upper and lower bounds VLSI Incidence geometry Transversality (mathematics) 1-planar graph Graph invariants Complete bipartite graph Complete graph Crossing number inequality Petersen graph Sociogram Chromatic number Endre Szemerédi Graph (discrete mathematics) NP-hard Constructivism (art) Convex polygon Geometric intersection Szemerédi-Trotter theorem Complete (complexity) Pappus graph McGee graph Václav Chvátal Distributed computing Heawood graph John Ernest Three utilities problem Edge (graph theory) F. Thomson Leighton Graph drawing Graph drawing Graph theory Hanani–Tutte theorem Tamal Dey Happy ending problem Coxeter graph Fixed-parameter tractable Albertson conjecture Topological graph theory K-set (geometry) Kazimierz Zarankiewicz Heuristic Planar graph Incidence (geometry) Michael Garey Miklós Ajtai On-line Encyclopedia of Integer Sequences World War II Sociology Vertex (graph theory) Thomas L. Saaty Planarization Existential theory of the reals Nauru graph

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 69 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software