Graph embedding (original) (raw)
In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: * the endpoints of the arc associated with an edge are the points associated with the end vertices of * no arcs include points associated with other vertices, * two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Property | Value |
---|---|
dbo:abstract | In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: * the endpoints of the arc associated with an edge are the points associated with the end vertices of * no arcs include points associated with other vertices, * two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold. Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space . A planar graph is one that can be embedded in 2-dimensional Euclidean space Often, an embedding is regarded as an equivalence class (under homeomorphisms of ) of representations of the kind just described. Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding". This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number". (en) En teoría de grafos topológica, un embebido (o también incrustación) de un grafo en una superficie es una representación de sobre en la que sus vértices están asociados con puntos de y sus lados se asocian con arcos simples (imágenes homeomórficas de ) de , de tal forma que: * Los extremos del arco asociado a un lado son los puntos asociados a los vértices extremos de * Ningún arco incluye puntos asociados a otros vértices * Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos Aquí se entiende por superficie una variedad de orden compacta y conexa. De manera informal, un embebido de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus lados se intersequen solo en sus puntos extremos. Es bien sabido que cualquier gráfico finito se puede incrustar en el espacio euclídeo tridimensional . Por definición, un grafo plano es aquel que se puede incrustar en un espacio euclídeo bidimensional A menudo, un embebido se considera una clase de equivalencia (bajo homeomorfismos de ) de las representaciones del tipo que se acaba de describir. Algunos autores definen una versión más débil de la definición de "embebido de grafos" al omitir la condición de no intersección para los lados. En tales contextos, la definición más estricta se describe como embebido de grafos sin cruces. Este artículo trata solo de la definición estricta de embebido de grafos. La definición más débil se discute en los artículos "dibujo de grafos" y "número de cruce". (es) Вложение графа — изучаемое в рамках топологической теории графов представление графа на заданной поверхности , в котором точки ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что: * конечные точки дуги, ассоциированной с ребром графа , являются точками, ассоциированными с конечными вершинами этого ребра графа * никакая дуга не содержит точки, ассоциированные с другими вершинами * никакие две дуги не пересекаются во внутренних точках этих дуг. Здесь поверхность является компактным, связным 2-мерным многообразием. Неформально, вложение графа в поверхность является изображением графа на поверхности таким образом, что его рёбра могут пересекаться только в конечных точках. Хорошо известно, что любой конечный граф может быть вложен в трёхмерное евклидово пространство , а планарные графы могут быть вложены в двумерное евклидово пространство . Часто вложение рассматривается как класс эквивалентности (по гомеоморфизмам ) представлений описанного вида. В контексте проблематики визуализации графов рассматривают также слабую версию определения вложения графа, в которой не требуется отсутствие пересечений рёбер. Соответственно, сильное определение описывается как «вложение графа без пересечений». (ru) У топологічній теорії графів, вкладення (також врізання) графа у поверхню Σ — це подання графа на Σ, де точки Σ асоціюються з вершинами, а прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що: * кінцеві точки дуги, які пов'язані з ребром , є точками, пов'язаними з кінцевими вершинами дуги * ніяка дуга не містить точок, асоційованих з іншими вершинами, * ніякі дві дуги не перетинаються у внутрішніх точках цих дуг. Тут поверхня є компактним, зв'язаним 2-многовидом. Неформально, вкладення графа в поверхню є зображенням графа на поверхні, побудоване так, що його ребра можуть перетинатися тільки в їхніх кінцевих точках. Відомо, що будь-який скінченний граф можна вкласти в 3-вимірний евклідів простір , а планарні графи можна вкласти у 2-вимірний евклідів простір . Часто вкладення розглядається, як клас еквівалентності (за гомеоморфізмами Σ) представлень описаного виду. Деякі автори дають слабшу версію визначення «вкладення графа», в якій не вимагається відсутність перетинів ребер. У цьому контексті сильніше визначення описується як «вкладення графа без перетинів». Ця стаття обговорює тільки строге визначення вкладення графа. Слабке визначення обговорюється в статтях «Візуалізація графів» і «Число схрещень». (uk) |
dbo:thumbnail | wiki-commons:Special:FilePath/Heawood_graph_and_map_on_torus.png?width=300 |
dbo:wikiPageID | 8149170 (xsd:integer) |
dbo:wikiPageLength | 13336 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1101880643 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Metaphor dbr:Minor_(graph_theory) dbr:Wendy_Myrvold dbr:Book_embedding dbr:Petersen_family dbr:Cubic_graph dbr:Double_exponential_function dbr:Doubly_connected_edge_list dbr:Compact_space dbr:Crossing_number_(graph_theory) dbr:General_position dbr:Genus_(mathematics) dbr:Petersen_graph dbr:Rotation_system dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:NP-hard dbr:Connected_space dbr:Linear_time dbr:Linkless_embedding dbr:Embedding dbr:Pappus_graph dbr:Plane_(geometry) dbc:Graph_algorithms dbr:Time_complexity dbr:Fáry's_theorem dbr:Gary_Miller_(computer_scientist) dbr:Cyclic_order dbr:Face_(graph_theory) dbr:Graph-encoded_map dbr:Graph_drawing dbr:Graph_theory dbr:John_Reif dbr:Fixed-parameter_tractability dbr:Regular_map_(graph_theory) dbr:ACM_Symposium_on_Theory_of_Computing dbc:Topological_graph_theory dbr:Surface_(mathematics) dbr:Homeomorphism dbr:Triangulation_(geometry) dbr:Manifold dbr:Planar_graph dbr:Polynomial_time dbr:Graph_thickness dbr:William_Lawrence_Kocay dbr:Moment_curve dbr:Topological_graph_theory dbr:Ribbon_graph dbr:Halfplane dbr:Book_thickness dbr:Klein_graph dbr:File:Heawood_graph_and_map_on_torus.png |
dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Main dbt:Reflist dbt:Short_description dbt:Use_American_English dbt:Use_mdy_dates |
dct:subject | dbc:Graph_algorithms dbc:Topological_graph_theory |
rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Procedure101023820 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:WikicatGraphInvariants yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
rdfs:comment | In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: * the endpoints of the arc associated with an edge are the points associated with the end vertices of * no arcs include points associated with other vertices, * two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold. (en) En teoría de grafos topológica, un embebido (o también incrustación) de un grafo en una superficie es una representación de sobre en la que sus vértices están asociados con puntos de y sus lados se asocian con arcos simples (imágenes homeomórficas de ) de , de tal forma que: * Los extremos del arco asociado a un lado son los puntos asociados a los vértices extremos de * Ningún arco incluye puntos asociados a otros vértices * Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos Aquí se entiende por superficie una variedad de orden compacta y conexa. (es) Вложение графа — изучаемое в рамках топологической теории графов представление графа на заданной поверхности , в котором точки ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что: * конечные точки дуги, ассоциированной с ребром графа , являются точками, ассоциированными с конечными вершинами этого ребра графа * никакая дуга не содержит точки, ассоциированные с другими вершинами * никакие две дуги не пересекаются во внутренних точках этих дуг. (ru) У топологічній теорії графів, вкладення (також врізання) графа у поверхню Σ — це подання графа на Σ, де точки Σ асоціюються з вершинами, а прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що: * кінцеві точки дуги, які пов'язані з ребром , є точками, пов'язаними з кінцевими вершинами дуги * ніяка дуга не містить точок, асоційованих з іншими вершинами, * ніякі дві дуги не перетинаються у внутрішніх точках цих дуг. Тут поверхня є компактним, зв'язаним 2-многовидом. (uk) |
rdfs:label | Grafo embebido (es) Graph embedding (en) Вложение графа (ru) Вкладення графа (uk) |
owl:sameAs | freebase:Graph embedding yago-res:Graph embedding wikidata:Graph embedding dbpedia-es:Graph embedding dbpedia-fa:Graph embedding dbpedia-ru:Graph embedding dbpedia-uk:Graph embedding https://global.dbpedia.org/id/4kcHL |
prov:wasDerivedFrom | wikipedia-en:Graph_embedding?oldid=1101880643&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Pappus-graph-on-torus.png wiki-commons:Special:FilePath/Petersen-graph.png wiki-commons:Special:FilePath/Heawood_graph_and_map_on_torus.png wiki-commons:Special:FilePath/Klein-map.png |
foaf:isPrimaryTopicOf | wikipedia-en:Graph_embedding |
is dbo:wikiPageRedirects of | dbr:Graph_genus dbr:Graph_imbedding dbr:Graphs_and_manifolds dbr:2-cell_embedding dbr:Determination_of_the_genus_of_a_graph dbr:Determining_the_genus_of_a_graph dbr:Closed_2-cell_embedding |
is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Barnette's_conjecture dbr:Bipartite_double_cover dbr:Book_embedding dbr:Dessin_d'enfant dbr:Apollonian_network dbr:Pathwidth dbr:Cubic_graph dbr:Cycle_double_cover dbr:Vizing's_theorem dbr:Doubly_connected_edge_list dbr:List_of_long_mathematical_proofs dbr:Pearls_in_Graph_Theory dbr:Robertson–Seymour_theorem dbr:Conway_polyhedron_notation dbr:Matroid_parity_problem dbr:Genus_(mathematics) dbr:Geometric_spanner dbr:Rotation_system dbr:Upward_planar_drawing dbr:Wilson_operation dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_minor dbr:Graph_structure_theorem dbr:Bouquet_graph dbr:Möbius_strip dbr:Cop_number dbr:Oriented_coloring dbr:Linkless_embedding dbr:Cactus_graph dbr:Snark_(graph_theory) dbr:Clique_complex dbr:Combinatorial_map dbr:Computers_and_Intractability dbr:Franklin_graph dbr:Kotzig's_theorem dbr:Planar_separator_theorem dbr:Spanning_tree dbr:Peripheral_cycle dbr:Acyclic_coloring dbr:Gain_graph dbr:Gödel's_speed-up_theorem dbr:Heawood_graph dbr:Johnson–Lindenstrauss_lemma dbr:Link_prediction dbr:Three_utilities_problem dbr:Dual_graph dbr:Duality_(mathematics) dbr:Outerplanar_graph dbr:Pancake_graph dbr:Pancake_sorting dbr:Goldberg–Coxeter_construction dbr:Graph-encoded_map dbr:Graph_drawing dbr:Graph_flattenability dbr:Graph_genus dbr:KBD_algorithm dbr:Knowledge_graph_embedding dbr:Regular_map_(graph_theory) dbr:Structural_rigidity dbr:Covering_graph dbr:Hypothetical_zeolite dbr:Sheaf_of_planes dbr:Joan_Hutchinson dbr:Laves_graph dbr:Bidimensionality dbr:Blossom_tree_(graph_theory) dbr:Blow-up_lemma dbr:Szilassi_polyhedron dbr:Homeomorphism_(graph_theory) dbr:Tietze's_graph dbr:Toroidal_graph dbr:CW_complex dbr:Planar_SAT dbr:Planar_graph dbr:Greedy_embedding dbr:Embedded dbr:Graph_imbedding dbr:Graphs_and_manifolds dbr:Map_(graph_theory) dbr:Euclidean_plane dbr:FKT_algorithm dbr:Planar_straight-line_graph dbr:Planarity_testing dbr:Sylvester–Gallai_theorem dbr:Planar_cover dbr:Möbius–Kantor_graph dbr:Nauru_graph dbr:Whitney's_planarity_criterion dbr:Topological_graph dbr:Petrie_dual dbr:Petrie_polygon dbr:Topological_graph_theory dbr:Ribbon_graph dbr:Wagner's_theorem dbr:Sparsity_matroid dbr:Spatial_embedding dbr:Xuong_tree dbr:2-cell_embedding dbr:Determination_of_the_genus_of_a_graph dbr:Determining_the_genus_of_a_graph dbr:Closed_2-cell_embedding |
is dbp:properties of | dbr:Möbius–Kantor_graph |
is foaf:primaryTopic of | wikipedia-en:Graph_embedding |