Outerplanar graph (original) (raw)
En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire.
| Property | Value |
|---|---|
| dbo:abstract | En teoría de grafos, un grafo plano exterior es un grafo que tiene una representación plana para la que todos los vértices pertenecen a la cara exterior del dibujo. Los grafos planos externos se pueden caracterizar (análogamente al teorema de Wagner para grafos planos) por los dos menores prohibidos K4 y K2,3, o por sus . Poseen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Cada grafo plano externo tiene 3 colores; y y como máximo 2. Los grafos planos exteriores son un subconjunto de los grafos planos, de los subgrafos de grafos serie-paralelo y de los . Los grafos planos exteriores máximos, aquellos a los que no se les pueden añadir más aristas conservando la planaridad exterior, también son y de visibilidad. (es) En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire. (fr) In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants.They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2. The outerplanar graphs are a subset of the planar graphs, the subgraphs of series–parallel graphs, and the circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also chordal graphs and visibility graphs. (en) В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані. Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2. Зовніпланарні графи є підмножиною планарних графів, підграфами паралельно-послідовних графів і колових графів. Максимальний зовніпланарний граф — це граф, до якого можна додати ребро без втрати зовніпланарності. Вони також є хордальними і . (uk) В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани. Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера.Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2. Внешнепланарные графы являются подмножеством планарных графов, подграфами параллельно-последовательных графов и круговых графов. Максимальный внешнепланарный граф — это граф, к которому нельзя добавить ребро без потери внешнепланарности. Они также являются хордальными и графами видимости. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Triangulation_3-coloring.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran http://www.graphclasses.org http://www.smc.math.ca/cjm/v22/p1082 http://www.numdam.org/item%3Fid=AIHPB_1967__3_4_433_0 http://www.graphclasses.org/classes/gc_110.html |
| dbo:wikiPageID | 352343 (xsd:integer) |
| dbo:wikiPageLength | 18423 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094649177 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Princeton_University dbr:Minor_(graph_theory) dbr:Biconnected_component dbr:Degeneracy_(graph_theory) dbc:Graph_families dbr:Perfect_matching dbr:Cycle_(graph_theory) dbr:Undirected_graph dbr:Vizing's_theorem dbr:Degree_(graph_theory) dbr:International_Journal_of_Computational_Geometry_and_Applications dbr:Kuratowski's_theorem dbr:1-planar_graph dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Crossing_number_(graph_theory) dbr:McGill_University dbr:Generalized_Petersen_graph dbr:Graph_coloring dbr:Boxicity dbr:NP-complete dbr:Linear_time dbr:Linkless_embedding dbr:Cactus_graph dbr:Halin_graph dbr:Simple_polygon dbr:Acta_Mathematica_Hungarica dbr:Tree_(graph_theory) dbr:Treewidth dbr:Triangle-free_graph dbr:Václav_Chvátal dbr:K-outerplanar_graph dbr:K-tree dbr:Lecture_Notes_in_Computer_Science dbr:Lecture_Notes_in_Mathematics dbr:Cycle_graph dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Graduate_Texts_in_Mathematics dbr:Graph_embedding dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_the_ACM dbr:Intersection_graph dbr:Chordal_graph dbr:Biconnected_graph dbr:Colin_de_Verdière_graph_invariant dbr:Homeomorphism_(graph_theory) dbr:Polygon_triangulation dbr:Dihedral_group dbr:Ars_Combinatoria_(journal) dbr:Art_gallery_theorem dbr:Planar_graph dbr:Society_for_Industrial_and_Applied_Mathematics dbr:Circle_graph dbr:Greedy_coloring dbr:Polynomial_time dbr:Canadian_Journal_of_Mathematics dbr:Chromatic_index dbr:Symposium_on_Theoretical_Aspects_of_Computer_Science dbr:Euclidean_plane dbr:Visibility_graph dbr:Series–parallel_graph dbr:Pancyclic_graph dbr:Wagner's_theorem dbr:Hamiltonian_cycle dbr:Breadth_first_search dbr:Forbidden_minor dbr:Planar_dual dbr:File:Finite-3-regular-graph-4-vertices.png dbr:File:Cactus_graph.svg dbr:File:Triangulation_3-coloring.svg |
| dbp:title | Outplanar Graph (en) |
| dbp:urlname | OutplanarGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_families dbc:Planar_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatGeometricGraphs yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire. (fr) En teoría de grafos, un grafo plano exterior es un grafo que tiene una representación plana para la que todos los vértices pertenecen a la cara exterior del dibujo. Los grafos planos externos se pueden caracterizar (análogamente al teorema de Wagner para grafos planos) por los dos menores prohibidos K4 y K2,3, o por sus . Poseen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Cada grafo plano externo tiene 3 colores; y y como máximo 2. (es) In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants.They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2. (en) В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані. Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2. (uk) В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани. Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера.Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2. (ru) |
| rdfs:label | Grafo plano exterior (es) Graphe planaire extérieur (fr) Outerplanar graph (en) Внешнепланарный граф (ru) Зовніпланарний граф (uk) |
| owl:sameAs | freebase:Outerplanar graph yago-res:Outerplanar graph wikidata:Outerplanar graph dbpedia-es:Outerplanar graph dbpedia-fr:Outerplanar graph dbpedia-hu:Outerplanar graph dbpedia-ru:Outerplanar graph dbpedia-uk:Outerplanar graph https://global.dbpedia.org/id/2tcFY |
| prov:wasDerivedFrom | wikipedia-en:Outerplanar_graph?oldid=1094649177&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cactus_graph.svg wiki-commons:Special:FilePath/Finite-3-regular-graph-4-vertices.png wiki-commons:Special:FilePath/Triangulation_3-coloring.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Outerplanar_graph |
| is dbo:wikiPageRedirects of | dbr:Outer_planar_graph dbr:Outerplanarity |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Book_embedding dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Area_(graph_drawing) dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Cycle_basis dbr:Defective_coloring dbr:Incidence_coloring dbr:Induced_subgraph_isomorphism_problem dbr:Robertson–Seymour_theorem dbr:(a,_b)-decomposition dbr:1-planar_graph dbr:Complete_bipartite_graph dbr:Neighbourhood_(graph_theory) dbr:Universal_point_set dbr:Upward_planar_drawing dbr:Chromatic_polynomial dbr:Glossary_of_graph_theory dbr:Graph_coloring_game dbr:Boxicity dbr:Equitable_coloring dbr:Apex_graph dbr:Linkless_embedding dbr:Cactus_graph dbr:Hamiltonian_completion dbr:Treewidth dbr:K-outerplanar_graph dbr:K-tree dbr:Dual_graph dbr:Forbidden_graph_characterization dbr:Angular_resolution_(graph_drawing) dbr:Harborth's_conjecture dbr:Tree-depth dbr:Reconstruction_conjecture dbr:Chordal_graph dbr:Colin_de_Verdière_graph_invariant dbr:Polygon_triangulation dbr:Planar_graph dbr:Circle_graph dbr:Circular_layout dbr:Metric_dimension_(graph_theory) dbr:Partial_k-tree dbr:Sum_coloring dbr:Series–parallel_graph dbr:Simultaneous_embedding dbr:Pancyclic_graph dbr:Outer_planar_graph dbr:Outerplanarity |
| is foaf:primaryTopic of | wikipedia-en:Outerplanar_graph |
