Planar graph (original) (raw)
Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla). Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals. En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior. Per poder comprovar la planaritat d'un graf, primer s'ha d'adequar a una sèrie de criteris bàsics: * El graf és connex. Si tenim un graf inconnex, podem considerar cada part com a graf connex independent. * No té cap vèrtex de grau 1. Si conté vèrtexs de grau 1, per tant amb una sola aresta, aquests es poden eliminar de l'estructura sense risc a modificar-ne la planaritat. (ca) Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží. (cs) في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط. (ar) Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden. (de) Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. (fr) En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos. Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de género arbitrario. En esta terminología, los grafos planos tienen género 0, por ser el plano y la esfera de género 0. (es) In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a planar map. Although a plane graph has an external or unbounded face, none of the faces of a planar map has a particular status. Planar graphs generalize to graphs drawable on a surface of a given genus. In this terminology, planar graphs have genus 0, since the plane (and the sphere) are surfaces of genus 0. See "graph embedding" for other related topics. (en) 평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다. 예를 들어 다음의 그래프는 모두 평면 그래프이다. * 평면 그래프의 예 * * 이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다. * 앞의 그래프와 같은 그래프이다. 한편 아래 그래프는 평면 그래프가 아니다. * 평면 그래프가 아닌 그래프의 예 * 꼭짓점이 5개인 완전 그래프 * 꼭짓점이 3개씩인 완전 이분 그래프 * 페테르센 그래프 엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다. (ko) Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano. Ad esempio sono planari i seguenti grafi: Il secondo può essere raffigurato senza archi che si intersecano spostando uno degli archi dati da una diagonale al di fuori del perimetro del quadrato. Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di archi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari: K5 K3,3 Si tratta del grafo completo con 5 nodi e del grafo bipartito completo con 3+3 nodi ; questi due grafi sono chiamati anche grafi di Kuratowski, in onore del matematico polacco Kazimierz Kuratowski. Si constata infatti che non è possibile ridisegnare queste raffigurazioni evitando che gli archi si intersechino. In effetti Kuratowski nel 1929 ha dimostrato che questi sono i due grafi non planari più ridotti, con il seguente enunciato. (it) 平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。極小な非平面的グラフは、K3,3とK5である。 (ja) Em Teoria dos Grafos, um grafo planar é um grafo que pode ser imerso no plano de tal forma que suas arestas não se cruzem, esta é uma idealização abstrata de um grafo plano, um grafo plano é um grafo planar que foi desenhado no plano sem o cruzamento de arestas. Aparentemente o estudo da planaridade de um grafo é uma questão topológica que se baseia em resultados como o Teorema da Curva de Jordan que de forma simplificada diz que uma curva fechada simples no plano divide-o em duas partes, apesar deste ser um critério muito importante, é natural o questionamento se há algum resultado combinatório que caracterize um grafo plano. Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porém apenas o que é desenhado sem cruzamento de arestas é um grafo plano. (pt) Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim. (pl) Inom grafteori är en planär graf en graf som kan i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna. En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna. Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa. En generalisering av planära grafer är grafer som kan ritas på en yta av ett givet genus. Med denna terminologi har planära grafer grafgenus 0, eftersom planet (och sfären) har genus 0. (sv) Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых. (ru) Планарний граф — граф, який може бути зображений на площині без перетину ребер. Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих. (uk) 在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。 藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。 平面圖可以被視為一個。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Butterfly_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://pigale.sourceforge.net http://cs.anu.edu.au/~bdm/plantri/%7Ctitle=A http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf%7Ctitle=Sur http://www.cc.gatech.edu/~bader/papers/planarity2003.html https://code.google.com/p/planarity/ http://ccl.northwestern.edu/netlogo/models/Planarity http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf%7Ctitle=On http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3/planarity.zip http://www.cut-the-knot.org/do_you_know/3Utilities.shtml https://web.archive.org/web/20160316171835/http:/www.cc.gatech.edu/~bader/papers/planarity2003.html http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/planar_graphs.html |
| dbo:wikiPageID | 24314 (xsd:integer) |
| dbo:wikiPageLength | 32775 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123061420 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_number dbr:Minor_(graph_theory) dbr:Mac_Lane's_planarity_criterion dbr:Meshedness_coefficient dbr:Topologically_equivalent dbr:Algorithm dbc:Graph_families dbr:Apollonian_network dbr:Homeomorphic dbr:Paul_Koebe dbr:Perspective_projection dbr:Petersen_family dbr:Regular_polygon dbr:Cycle_(graph_theory) dbr:Cycle_space dbr:Integer_lattice dbr:Kuratowski's_theorem dbr:Line_segment dbr:Robertson–Seymour_theorem dbr:1-planar_graph dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Connectivity_(graph_theory) dbr:Mathematical_induction dbr:Genus_(mathematics) dbr:Rotation_system dbr:Universal_point_set dbr:Upward_planar_drawing dbr:Clique-sum dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Graph_product dbr:NP-complete dbr:Convex_polygon dbr:Thickness_(graph_theory) dbr:Equivalence_class dbr:Apex_graph dbr:Line_graph dbr:Linkless_embedding dbr:Stereographic_projection dbr:Combinatorial_map dbr:Halin_graph dbr:Planar_separator_theorem dbr:Planarity dbr:Plane_(geometry) dbr:Simple_polygon dbr:Sprouts_(game) dbr:Steinitz's_theorem dbr:Thue_number dbr:Peripheral_cycle dbr:Butterfly_graph dbr:Torus dbr:Tree_(graph_theory) dbr:Treewidth dbr:Fáry's_theorem dbr:K-tree dbr:K-vertex-connected_graph dbr:Linking_number dbr:Three_utilities_problem dbr:Dual_graph dbr:Face_(graph_theory) dbr:Forbidden_graph_characterization dbr:Bridge_(graph_theory) dbr:Osculating_circle dbr:Outerplanar_graph dbr:Four_color_theorem dbr:Graph_embedding dbr:Graph_genus dbr:Graph_isomorphism_problem dbr:Graph_theory dbr:Hanani–Tutte_theorem dbr:Isomorphism dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Fraysseix–Rosenstiehl_planarity_criterion dbr:Order_dimension dbr:Intersection_graph dbr:Plane_curve dbr:Asymptotic_analysis dbr:Chordal_graph dbr:Kazimierz_Kuratowski dbr:Big_O_notation dbc:Intersection_classes_of_graphs dbr:Colin_de_Verdière_graph_invariant dbr:Homeomorphism dbr:Toroidal_graph dbr:Directed_acyclic_graph dbr:Map_graph dbr:Poland dbr:Sphere dbr:Circle_packing_theorem dbr:Circuit_rank dbr:Convex_polyhedron dbr:If_and_only_if dbr:Schlegel_diagram dbr:Utility_graph dbr:Euler_characteristic dbr:Planarization dbr:Planar_straight-line_graph dbr:Planarity_testing dbr:Whitney's_planarity_criterion dbr:Schnyder's_theorem dbr:Polyhedral_graph dbr:Tutte_embedding dbr:Strangulated_graph dbr:Universal_graph dbr:Scheinerman's_conjecture dbr:Wagner's_theorem dbr:Word-representable_graph dbr:Simple_graph dbr:Klaus_Wagner_(mathematician) dbr:Forbidden_minor dbr:Branch-width dbr:Sparse_graph dbr:Subdivision_(graph_theory) dbr:File:Dodecahedron_schlegel.svg dbr:File:CGK4PLN.svg dbr:File:Dual_graphs.svg dbr:File:Kuratowski.gif dbr:File:Nonplanar_no_subgraph_K_3_3.svg dbr:File:Butterfly_graph.svg dbr:File:Circle_packing_theorem_K5_minus_edge_example.svg dbr:File:Goldner-Harary_graph.svg dbr:File:Biclique_K_3_3.svg dbr:File:Complete_graph_K5.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_techreport dbt:Tesseract_graph_nonplanar_visual_proof.svg dbt:Citation dbt:Commons_category dbt:Main dbt:Math dbt:Mvar dbt:Radic dbt:Redirect dbt:Short_description dbt:Sub dbt:Sup |
| dct:subject | dbc:Graph_families dbc:Planar_graphs dbc:Intersection_classes_of_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Graph107000195 yago:Group100031264 yago:WikicatGeometricGraphs yago:WikicatIntersectionClassesOfGraphs yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží. (cs) في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط. (ar) Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden. (de) Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. (fr) 평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다. 예를 들어 다음의 그래프는 모두 평면 그래프이다. * 평면 그래프의 예 * * 이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다. * 앞의 그래프와 같은 그래프이다. 한편 아래 그래프는 평면 그래프가 아니다. * 평면 그래프가 아닌 그래프의 예 * 꼭짓점이 5개인 완전 그래프 * 꼭짓점이 3개씩인 완전 이분 그래프 * 페테르센 그래프 엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다. (ko) 平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。極小な非平面的グラフは、K3,3とK5である。 (ja) Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim. (pl) Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых. (ru) Планарний граф — граф, який може бути зображений на площині без перетину ребер. Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих. (uk) 在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。 藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。 平面圖可以被視為一個。 (zh) En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla). Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals. En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior. (ca) En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos. (es) In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. (en) Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano. Ad esempio sono planari i seguenti grafi: Il secondo può essere raffigurato senza archi che si intersecano spostando uno degli archi dati da una diagonale al di fuori del perimetro del quadrato. Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di archi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari: K5 K3,3 (it) Inom grafteori är en planär graf en graf som kan i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna. En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna. Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa. (sv) Em Teoria dos Grafos, um grafo planar é um grafo que pode ser imerso no plano de tal forma que suas arestas não se cruzem, esta é uma idealização abstrata de um grafo plano, um grafo plano é um grafo planar que foi desenhado no plano sem o cruzamento de arestas. Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porém apenas o que é desenhado sem cruzamento de arestas é um grafo plano. (pt) |
| rdfs:label | مخطط مستو (ar) Graf pla (ca) Rovinný graf (cs) Planarer Graph (de) Grafo plano (es) Graphe planaire (fr) Grafo planare (it) 平面グラフ (ja) 평면 그래프 (ko) Planar graph (en) Graf planarny (pl) Grafo planar (pt) Планарный граф (ru) Planär graf (sv) Планарний граф (uk) 平面图 (图论) (zh) |
| owl:sameAs | freebase:Planar graph yago-res:Planar graph wikidata:Planar graph dbpedia-ar:Planar graph dbpedia-ca:Planar graph dbpedia-cs:Planar graph dbpedia-de:Planar graph dbpedia-es:Planar graph dbpedia-et:Planar graph dbpedia-fa:Planar graph dbpedia-fr:Planar graph dbpedia-he:Planar graph dbpedia-hr:Planar graph dbpedia-hu:Planar graph dbpedia-it:Planar graph dbpedia-ja:Planar graph dbpedia-ko:Planar graph http://lt.dbpedia.org/resource/Plokščiasis_grafas http://lv.dbpedia.org/resource/Planārs_grafs dbpedia-nn:Planar graph dbpedia-pl:Planar graph dbpedia-pt:Planar graph dbpedia-ro:Planar graph dbpedia-ru:Planar graph dbpedia-sk:Planar graph dbpedia-sl:Planar graph dbpedia-sr:Planar graph dbpedia-sv:Planar graph dbpedia-th:Planar graph dbpedia-uk:Planar graph http://ur.dbpedia.org/resource/مسطح_گراف dbpedia-vi:Planar graph dbpedia-zh:Planar graph https://global.dbpedia.org/id/4jwF4 |
| prov:wasDerivedFrom | wikipedia-en:Planar_graph?oldid=1123061420&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Biclique_K_3_3.svg wiki-commons:Special:FilePath/Butterfly_graph.svg wiki-commons:Special:FilePath/CGK4PLN.svg wiki-commons:Special:FilePath/Circle_packing_theorem_K5_minus_edge_example.svg wiki-commons:Special:FilePath/Complete_graph_K5.svg wiki-commons:Special:FilePath/Dodecahedron_schlegel.svg wiki-commons:Special:FilePath/Dual_graphs.svg wiki-commons:Special:FilePath/Goldner-Harary_graph.svg wiki-commons:Special:FilePath/Kuratowski.gif wiki-commons:Special:FilePath/Nonplanar_no_subgraph_K_3_3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Planar_graph |
| is dbo:wikiPageDisambiguates of | dbr:Planar |
| is dbo:wikiPageRedirects of | dbr:Convex_plane_graph dbr:Nonplanar_graph dbr:Kuratowski's_reduction_theorem dbr:Maximal_planar_graph dbr:Planar_Graph dbr:Planer_graph dbr:Triangular_graph dbr:Planar_graphs dbr:Plane_triangulation dbr:Nonplanar dbr:Planar_embedding dbr:Planar_embedding_of_the_graph dbr:Planar_map dbr:Planarity_(graph_theory) dbr:Plane_graph dbr:Wagner_theorem dbr:Outplanar_graph dbr:Theorem_P |
| is dbo:wikiPageWikiLink of | dbr:Bend_minimization dbr:Pyramid_(geometry) dbr:Queue_number dbr:Eodermdrome dbr:Menger_sponge dbr:Moser_spindle dbr:Mostow_rigidity_theorem dbr:Nowhere-zero_flow dbr:Mac_Lane's_planarity_criterion dbr:Meredith_graph dbr:Meshedness_coefficient dbr:Shallow_minor dbr:Convex_plane_graph dbr:Nonplanar_graph dbr:1930_in_science dbr:Barnette's_conjecture dbr:Bipartite_half dbr:Book_embedding dbr:Brenda_Baker dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Dense_subgraph dbr:Desargues_graph dbr:Antiprism_graph dbr:Apollonian_network dbr:Arboricity dbr:Arc_diagram dbr:Archimedean_graph dbr:Hosoya_index dbr:Hypercube_graph dbr:Jordan_curve_theorem dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Perfect_matching dbr:Petersen's_theorem dbr:Petersen_family dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Ring_lemma dbr:Cube dbr:Cycle_basis dbr:Cycle_graph_(algebra) dbr:Cycle_space dbr:Unit_distance_graph dbr:Vertex_cover dbr:Vizing's_theorem dbr:Dominance_drawing dbr:Dot_product_representation_of_a_graph dbr:Double-star_snark dbr:Doubly_connected_edge_list dbr:Dürer_graph dbr:Incidence_and_Symmetry_in_Design_and_Architecture dbr:Independent_set_(graph_theory) dbr:Index_of_electrical_engineering_articles dbr:Intersection_number_(graph_theory) dbr:Introduction_to_Circle_Packing dbr:Inversive_distance dbr:Kuratowski's_theorem dbr:Polyhedron dbr:Library_of_Efficient_Data_types_and_Algorithms dbr:List_of_graphs_by_edges_and_vertices dbr:Pearls_in_Graph_Theory dbr:Penny_graph dbr:Poussin_graph dbr:Pseudoforest dbr:Kuratowski's_reduction_theorem dbr:Robertson–Seymour_theorem dbr:String_diagram dbr:When_Topology_Meets_Chemistry dbr:Wiener–Araya_graph dbr:(a,_b)-decomposition dbr:1-planar_graph dbr:142_(number) dbr:Color-coding dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Computing_the_permanent dbr:Connectivity_(graph_theory) dbr:Crossing_number_(graph_theory) dbr:Crossing_number_inequality dbr:Matching_(graph_theory) dbr:Matroid_parity_problem dbr:Maximal_independent_set dbr:Maximal_planar_graph dbr:Maximum_cut dbr:Errera_graph dbr:Genus_(mathematics) dbr:Geodetic_graph dbr:Geometric_graph_theory dbr:Nearest_neighbor_graph dbr:Neighbourhood_(graph_theory) dbr:Network_analysis_(electrical_circuits) dbr:Orientation_(graph_theory) dbr:Petersen_graph dbr:Universal_point_set dbr:Tait's_conjecture dbr:Upward_planar_drawing dbr:Quotient_graph dbr:Radio_coloring dbr:Zdeněk_Dvořák dbr:Chromatic_polynomial dbr:Clique-sum dbr:Clique_problem dbr:Friendship_graph dbr:Girth_(graph_theory) dbr:Glossary_of_electrical_and_electronics_engineering dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Graph_bandwidth dbr:Graph_coloring dbr:Graph_coloring_game dbr:Graph_minor dbr:Graph_power dbr:Graph_structure_theorem dbr:Bounded_expansion dbr:Boxicity dbr:Branch-decomposition dbr:Möbius_ladder dbr:Möbius_strip dbr:Conflict-free_coloring dbr:Contact_graph dbr:Convex_drawing dbr:Convex_embedding dbr:Cop_number dbr:Crossing_Numbers_of_Graphs dbr:Thickness_(graph_theory) dbr:Erdős–Gyárfás_conjecture dbr:Erdős–Pósa_theorem dbr:Erdős–Ulam_problem dbr:Pseudotriangle dbr:Planar_Graph dbr:Planer_graph dbr:Apex_graph dbr:Baxter_permutation dbr:Bentley–Ottmann_algorithm dbr:Leonhard_Euler dbr:Line_graph dbr:Link_grammar dbr:Linkless_embedding dbr:Cactus_graph dbr:Chordal_completion dbr:Slope_number dbr:Snark_(graph_theory) dbr:Clebsch_graph dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Clustered_planarity dbr:Combinatorial_map dbr:Complexity_class dbr:Emanuels_Grīnbergs dbr:Feedback_arc_set dbr:Frucht's_theorem dbr:Frucht_graph dbr:Fullerene dbr:Halin's_grid_theorem dbr:Halin_graph dbr:Hamiltonian_decomposition dbr:Hamiltonian_path_problem dbr:Harries–Wong_graph dbr:Kepler–Poinsot_polyhedron dbr:Kotzig's_theorem dbr:Pfaffian dbr:Planar dbr:Planar_separator_theorem dbr:Planarity dbr:Spanning_tree dbr:Steinitz's_theorem dbr:String_graph dbr:Succinct_data_structure dbr:Matching_polynomial dbr:Matroid dbr:Matroid_minor dbr:Maze_generation_algorithm dbr:Szekeres_snark dbr:Peripheral_cycle dbr:Axonometry dbr:Brigitte_Servatius dbr:Butterfly_graph dbr:Acyclic_orientation dbr:Certifying_algorithm dbr:Tree_(graph_theory) dbr:Treewidth dbr:Triangle-free_graph dbr:Triangular_graph dbr:Truncated_tetrahedron dbr:Wagner_graph dbr:Well-covered_graph dbr:Wheel_graph dbr:Dissociation_number dbr:Distinguishing_coloring dbr:Dividing_a_circle_into_areas dbr:Fáry's_theorem dbr:GNRS_conjecture dbr:Gallery_of_named_graphs dbr:K-edge-connected_graph dbr:K-minimum_spanning_tree dbr:K-outerplanar_graph dbr:K-tree dbr:K-vertex-connected_graph dbr:Laman_graph dbr:Lattice_graph dbr:List_coloring dbr:Locally_linear_graph dbr:Minimum-weight_triangulation dbr:Partial_cube dbr:Takao_Nishizeki dbr:Three_utilities_problem dbr:Trémaux_tree dbr:Unrooted_binary_tree dbr:4 dbr:5 dbr:Alex_Stenzel dbr:Air_Transport_Network dbr:Dual_graph dbr:Duality_(mathematics) dbr:Edge_coloring dbr:Alternating_knot dbr:Ernst_Steinitz dbr:Euclidean_minimum_spanning_tree dbr:Forbidden_graph_characterization dbr:Angular_resolution_(graph_drawing) dbr:Barnette–Bosák–Lederberg_graph dbr:Brendan_McKay_(mathematician) dbr:Null_graph dbr:Otakar_Borůvka dbr:Outerplanar_graph dbr:Danilo_Blanuša dbr:Discharging_method_(discrete_mathematics) dbr:Flower_snark dbr:Force-directed_graph_drawing dbr:Four_color_theorem dbr:Goldberg–Seymour_conjecture dbr:Goldner–Harary_graph dbr:Golomb_graph dbr:Good_spanning_tree dbr:Graph_Theory,_1736–1936 dbr:Graph_drawing dbr:Graph_embedding dbr:Graph_isomorphism_problem dbr:Graph_partition dbr:Graph_property dbr:Graph_theory dbr:Graphic_matroid dbr:Gray_graph dbr:Hanani–Tutte_theorem dbr:Harborth's_conjecture dbr:Ising_model dbr:Kelmans–Seymour_conjecture dbr:Kieka_Mynhardt dbr:Kinetic_Euclidean_minimum_spanning_tree dbr:King's_graph dbr:Left-right_planarity_test dbr:List_of_Martin_Gardner_Mathematical_Games_columns dbr:Order_dimension dbr:Primal_graph dbr:Reachability dbr:Reconstruction_conjecture dbr:Regular_map_(graph_theory) dbr:Representation_(mathematics) dbr:Grötzsch's_theorem dbr:Hadwiger_number dbr:Haim_Hanani dbr:Hamiltonian_path dbr:Harries_graph dbr:Intersection_graph dbr:István_Fáry dbr:Itai_Benjamini dbr:JTS_Topology_Suite dbr:Baker's_technique dbr:Covering_graph dbr:Tetrahedron dbr:Hypergraph dbr:Hypohamiltonian_graph dbr:Pebble_game dbr:Uniquely_colorable_graph dbr:Thrackle dbr:Squaregraph dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Chennai_Mathematical_Institute dbr:Chordal_graph dbr:Albertson_conjecture dbr:John_Hopcroft dbr:János_Pach dbr:Kazimierz_Kuratowski dbr:Ladder_graph dbr:Bidiakis_cube dbr:Bidimensionality dbr:Bipartite_graph dbr:Bipartite_matroid dbr:Bipolar_orientation dbr:Block_graph dbr:Cograph dbr:Colin_de_Verdière_graph_invariant dbr:Ed_Scheinerman dbr:Edge_(geometry) dbr:Edge_cycle_cover dbr:Edge_dominating_set dbr:Herbert_Grötzsch dbr:Hereditary_property dbr:Herschel_graph |
| is dbp:properties of | dbr:Moser_spindle dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Cube dbr:Dürer_graph dbr:Poussin_graph dbr:Wiener–Araya_graph dbr:Errera_graph dbr:Friendship_graph dbr:Butterfly_graph dbr:Truncated_tetrahedron dbr:Wheel_graph dbr:Barnette–Bosák–Lederberg_graph dbr:Goldner–Harary_graph dbr:Tetrahedron dbr:Ladder_graph dbr:Bidiakis_cube dbr:Herschel_graph dbr:Diamond_graph dbr:Dipole_graph dbr:Bull_graph dbr:Walther_graph dbr:Tutte_graph dbr:Tadpole_graph |
| is rdfs:seeAlso of | dbr:Euler_characteristic |
| is foaf:primaryTopic of | wikipedia-en:Planar_graph |
