Tutte embedding (original) (raw)
En dibujo de grafos y en , un embebido de Tutte o incrustación baricéntrica de un grafo plano simple es un embebido de líneas rectas sin cruces con las propiedades de que la cara exterior es un polígono convexo y de que cada vértice interior está en el centroide (o baricentro) de las posiciones de sus vecinos. Si el polígono exterior es fijo, esta condición en los vértices interiores determina su posición únicamente como solución a un sistema de ecuaciones lineales. Resolver las ecuaciones geométricamente produce un embebido plano. El teorema del resorte de Tutte, probado por , establece que esta solución única siempre está libre de cruces, y como una condición más fuerte, que cada cara del embebido plano resultante es convexa. Se llama el teorema del resorte porque dicho embebido se pue
| Property | Value |
|---|---|
| dbo:abstract | En dibujo de grafos y en , un embebido de Tutte o incrustación baricéntrica de un grafo plano simple es un embebido de líneas rectas sin cruces con las propiedades de que la cara exterior es un polígono convexo y de que cada vértice interior está en el centroide (o baricentro) de las posiciones de sus vecinos. Si el polígono exterior es fijo, esta condición en los vértices interiores determina su posición únicamente como solución a un sistema de ecuaciones lineales. Resolver las ecuaciones geométricamente produce un embebido plano. El teorema del resorte de Tutte, probado por , establece que esta solución única siempre está libre de cruces, y como una condición más fuerte, que cada cara del embebido plano resultante es convexa. Se llama el teorema del resorte porque dicho embebido se puede encontrar como la posición de equilibrio para un sistema de resortes que representa los bordes del grafo. (es) In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average (or barycenter) of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte, states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph. (en) Вложение Татта (барицентричное вложение) простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение. Теорема Татта «о резиновой укладке» утверждает, что в единственном решении никогда нет пересечений рёбер и, что более строго, что любая грань получающегося планарного вложения выпукла. Вложение называется «резиновым», поскольку такое вложение может быть найдено как равновесное положение системы пружин или резиновых ремней, представляющих рёбра графа. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tutte_cube.svg?width=300 |
| dbo:wikiPageID | 39503349 (xsd:integer) |
| dbo:wikiPageLength | 14789 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102260533 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mesh_generation dbr:Spring_(device) dbr:Quadrilateral_mesh dbc:Planar_graphs dbr:Genus_(mathematics) dbr:Geometric_graph_theory dbr:Gaussian_elimination dbr:Geodesics dbr:Convex_embedding dbr:Convex_hull dbr:Convex_polygon dbr:Linear_equation dbr:Simplex dbr:Steinitz's_theorem dbr:Surface_(topology) dbr:Centroid dbr:Dual_polyhedron dbr:Fáry's_theorem dbr:K-vertex-connected_graph dbr:Laplacian_smoothing dbr:Lloyd's_algorithm dbr:Dual_graph dbc:Graph_drawing dbr:Force-directed_graph_drawing dbr:Graph_drawing dbr:Toroidal_graph dbr:Planar_graph dbr:Convex_polyhedron dbr:Polynomial_time dbr:Schlegel_diagram dbr:Unit_square dbr:Vertex_(graph_theory) dbr:Finite_element_method dbr:Non-positive_curvature dbr:Polyhedral_graph dbr:Polytope dbr:System_of_linear_equations dbr:Simple_graph dbr:File:Tutte_cube.svg dbr:Maxwell–Cremona_correspondence |
| dbp:authorlink | W. T. Tutte (en) |
| dbp:first | W. T. (en) |
| dbp:last | Tutte (en) |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description dbt:Harvs |
| dbp:year | 1963 (xsd:integer) |
| dcterms:subject | dbc:Planar_graphs dbc:Graph_drawing |
| gold:hypernym | dbr:Polygon |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | En dibujo de grafos y en , un embebido de Tutte o incrustación baricéntrica de un grafo plano simple es un embebido de líneas rectas sin cruces con las propiedades de que la cara exterior es un polígono convexo y de que cada vértice interior está en el centroide (o baricentro) de las posiciones de sus vecinos. Si el polígono exterior es fijo, esta condición en los vértices interiores determina su posición únicamente como solución a un sistema de ecuaciones lineales. Resolver las ecuaciones geométricamente produce un embebido plano. El teorema del resorte de Tutte, probado por , establece que esta solución única siempre está libre de cruces, y como una condición más fuerte, que cada cara del embebido plano resultante es convexa. Se llama el teorema del resorte porque dicho embebido se pue (es) In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average (or barycenter) of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte, states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can b (en) Вложение Татта (барицентричное вложение) простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение. Теорема Татта «о резиновой укладке» утверждает, что в единственном решении никогда нет пересечений рёбер и, что более строго, что любая грань получающегося планарного вложения выпукла. Вложение называется «резиновым», поскольку такое вложение может быть найдено как равновесное положение системы пруж (ru) |
| rdfs:label | Embebido de Tutte (es) Вложение Татта (ru) Tutte embedding (en) |
| owl:sameAs | freebase:Tutte embedding yago-res:Tutte embedding wikidata:Tutte embedding dbpedia-es:Tutte embedding dbpedia-ru:Tutte embedding https://global.dbpedia.org/id/fkUv |
| prov:wasDerivedFrom | wikipedia-en:Tutte_embedding?oldid=1102260533&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tutte_cube.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tutte_embedding |
| is dbo:knownFor of | dbr:W._T._Tutte |
| is dbo:wikiPageRedirects of | dbr:Tutte's_spring_theorem |
| is dbo:wikiPageWikiLink of | dbr:Geometry_processing dbr:Steinitz's_theorem dbr:W._T._Tutte dbr:K-vertex-connected_graph dbr:Lami's_theorem dbr:Laplacian_smoothing dbr:Force-directed_graph_drawing dbr:Planar_graph dbr:Polyhedral_graph dbr:Tutte's_spring_theorem |
| is dbp:knownFor of | dbr:W._T._Tutte |
| is foaf:primaryTopic of | wikipedia-en:Tutte_embedding |
