Apex graph (original) (raw)
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. Apex graphs are closed under the operation of taking minors and play a role in several other aspects of graph minor theory: linkless embedding, Hadwiger's conjecture, YΔY-reducible graphs, and relations between treewidth and graph diameter. (en) En teoría de grafos, una rama de las matemáticas, un grafo de ápice (o también grafo apical o grafo de vértice) es un tipo de grafo que puede convertirse en un grafo plano mediante la eliminación de un solo vértice. El vértice eliminado se llama ápice del grafo. Es "un" ápice, y no "el" ápice, porque uno de estos grafos puede tener más de uno, como por ejemplo en el caso de los grafos mínimos no planos K5 o K3,3, en los que cada vértice es un ápice. Los grafos de ápice incluyen grafos que en sí mismos son planos, en cuyo caso nuevamente cada vértice es un ápice. El grafo nulo también se cuenta como un grafo de ápice aunque no tenga ningún vértice para eliminar. Son bajo la operación de tomar menores y juegan un papel considerable en varios otros aspectos de la teoría de grafos menores: los embebidos sin enlaces, la , los grafos YΔY-reducibles, y su relación con el y con el diámetro de un grafo. (es) В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины. Удалённая вершина называется верхушкой графа. Заметим, что верхушка может быть не одна. Например, в минимальном непланарном графе K5 или K3,3 каждая вершина является верхушкой. Верхушечные графы включают изначально планарные графы, в которых каждая вершина является верхушкой. Нуль-граф считается также верхушечным, хотя в нём нет вершин для удаления. Верхушечные графы замкнуты относительно операции образования миноров и играют большую роль в некоторых других аспектах теории миноров графов, включая незацепленное вложение, гипотезу Хадвигера, YΔY-сводимые графы и связь между древесной шириной и диаметром графа. (ru) В теорії графів верхівковий граф — це граф, який можна зробити планарним видаленням однієї вершини. Видалену вершину називають верхівкою графа. Зауважимо, що верхівка може бути не одна. Наприклад, у мінімальному непланарному графі K5 або K3,3 кожна вершина є верхівкою. Верхівкові графи включають початково планарні графи, в яких кожна вершина є верхівкою. Нуль-граф вважається також верхівковим, хоча в ньому немає вершин для видалення. Верхівкові графи замкнуті відносно операції утворення мінорів і грають важливу роль у деяких інших аспектах теорії мінорів графів, таких як незачеплене вкладення, гіпотеза Хадвігера, YΔY-звідні графи і зв'язок між деревною шириною і діаметром графа. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Apex_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf http://research.nii.ac.jp/~k_keniti/focsfinal.pdf http://www.cse.ucsd.edu/users/russell/arvind.ps http://www.csuchico.edu/~tmattman/mpthesis.pdf http://erikdemaine.org/papers/ApexMinorFree_ICALP2009/paper.pdf http://erikdemaine.org/papers/GenApprox_SODA2005/ http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf https://web.archive.org/web/20120314072225/http:/www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM10_SoCG10_Cabello_crossingNumberHard.pdf https://web.archive.org/web/20170922003345/http:/www.fmf.uni-lj.si/~mohar/Papers/ApexGenus.pdf https://web.archive.org/web/20181211095652/http:/erikdemaine.org/papers/GenApprox_SODA2005/ http://portal.acm.org/citation.cfm%3Fid=1496812 http://www.fmf.uni-lj.si/~mohar/Papers/ApexGenus.pdf http://www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM10_SoCG10_Cabello_crossingNumberHard.pdf |
| dbo:wikiPageID | 28228942 (xsd:integer) |
| dbo:wikiPageLength | 24479 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097173796 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Projective_plane dbr:Algorithmica dbc:Graph_families dbc:Graph_minor_theory dbr:Hypercube_graph dbr:Pathwidth dbr:Petersen_family dbr:Rhombic_dodecahedron dbr:Cube dbr:Degree_(graph_theory) dbr:Robertson–Seymour_theorem dbc:Planar_graphs dbr:Complete_graph dbr:Genus_(mathematics) dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Graph_minor dbr:Graph_structure_theorem dbr:Möbius_ladder dbr:Möbius_strip dbr:NP-complete dbr:NP-hard dbr:Linear_time dbr:Linkless_embedding dbr:Closure_(mathematics) dbr:Combinatorica dbr:Complement_graph dbr:Travelling_salesman_problem dbr:Treewidth dbr:Triangle-free_graph dbr:Wheel_graph dbr:K-vertex-connected_graph dbr:Forbidden_graph_characterization dbr:Null_graph dbr:Outerplanar_graph dbr:Four_color_theorem dbr:Graph_drawing dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_the_ACM dbr:Fixed-parameter_tractability dbr:Hadwiger_conjecture_(graph_theory) dbr:Bidimensionality dbr:Distance_(graph_theory) dbr:Bulletin_of_the_American_Mathematical_Society dbr:Planar_graph dbr:Polynomial-time_approximation_scheme dbr:SPQR_tree dbr:Vertex_(graph_theory) dbr:Polyhedral_graph dbr:Y-Δ_transform dbr:Hamiltonian_cycle dbr:Grid_graph dbr:Polyhedral_pyramid dbr:File:Apex_graph.svg dbr:File:Apex_rhombic_dodecahedron.svg dbr:File:Moebius-ladder-16.svg |
| dbp:last | Thomas (en) Robertson (en) Seymour (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Sfrac dbt:Short_description dbt:Sub dbt:Harvs dbt:Unsolved |
| dbp:year | 1993 (xsd:integer) |
| dct:subject | dbc:Graph_families dbc:Graph_minor_theory dbc:Planar_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. (en) En teoría de grafos, una rama de las matemáticas, un grafo de ápice (o también grafo apical o grafo de vértice) es un tipo de grafo que puede convertirse en un grafo plano mediante la eliminación de un solo vértice. El vértice eliminado se llama ápice del grafo. Es "un" ápice, y no "el" ápice, porque uno de estos grafos puede tener más de uno, como por ejemplo en el caso de los grafos mínimos no planos K5 o K3,3, en los que cada vértice es un ápice. Los grafos de ápice incluyen grafos que en sí mismos son planos, en cuyo caso nuevamente cada vértice es un ápice. El grafo nulo también se cuenta como un grafo de ápice aunque no tenga ningún vértice para eliminar. (es) В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины. Удалённая вершина называется верхушкой графа. Заметим, что верхушка может быть не одна. Например, в минимальном непланарном графе K5 или K3,3 каждая вершина является верхушкой. Верхушечные графы включают изначально планарные графы, в которых каждая вершина является верхушкой. Нуль-граф считается также верхушечным, хотя в нём нет вершин для удаления. (ru) В теорії графів верхівковий граф — це граф, який можна зробити планарним видаленням однієї вершини. Видалену вершину називають верхівкою графа. Зауважимо, що верхівка може бути не одна. Наприклад, у мінімальному непланарному графі K5 або K3,3 кожна вершина є верхівкою. Верхівкові графи включають початково планарні графи, в яких кожна вершина є верхівкою. Нуль-граф вважається також верхівковим, хоча в ньому немає вершин для видалення. (uk) |
| rdfs:label | Apex graph (en) Grafo de ápice (es) Верхушечный граф (ru) Верхівковий граф (uk) |
| owl:sameAs | freebase:Apex graph yago-res:Apex graph wikidata:Apex graph dbpedia-es:Apex graph dbpedia-hu:Apex graph dbpedia-ru:Apex graph dbpedia-uk:Apex graph https://global.dbpedia.org/id/4RQ98 |
| prov:wasDerivedFrom | wikipedia-en:Apex_graph?oldid=1097173796&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Apex_graph.svg wiki-commons:Special:FilePath/Apex_rhombic_dodecahedron.svg wiki-commons:Special:FilePath/Moebius-ladder-16.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Apex_graph |
| is dbo:wikiPageDisambiguates of | dbr:Apex |
| is dbo:wikiPageWikiLink of | dbr:Pyramid_(geometry) dbr:Petersen_family dbr:Robertson–Seymour_theorem dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Graph_structure_theorem dbr:Möbius_ladder dbr:Linkless_embedding dbr:Treewidth dbr:Wagner_graph dbr:Forbidden_graph_characterization dbr:Hadwiger_number dbr:Bidimensionality dbr:Planar_graph dbr:Apex dbr:List_of_unsolved_problems_in_mathematics dbr:Planar_cover dbr:Universal_vertex |
| is dbp:properties of | dbr:Möbius_ladder dbr:Wagner_graph |
| is foaf:primaryTopic of | wikipedia-en:Apex_graph |
