Squaregraph (original) (raw)
In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face.
| Property | Value |
|---|---|
| dbo:abstract | En teoría de grafos, un grafo cuadrado es un grafo no dirigido que puede dibujarse en el plano de modo que cada superficie acotada es un cuadrilátero y cada vértice con tres o menos vecinos es incidente a una cara no acotada. Los grafos cuadrados son un tipo de grafos medianos planares, e incluyen como casos especiales a los árboles, , y los grafos de los poliominós. Muchos problemas algorítmicos pueden ser computados más eficientemente en el contexto de grafos cuadrados que en casos más generales de grafos medianos o planares. Por ejemplo, y presentan algoritmos en tiempo lineal para computar el diámetro de grafos cuadrados, y para encontrar la distancia máxima a todos los demás vértices. (es) In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face. (en) В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани. (ru) У теорії графів рамковим графом називають вид неорієнтованого графа, який можна намалювати на площині таким способом, що будь-яка обмежена грань є чотирикутником і будь-яка вершина з трьома і менше сусідами інцидентна необмеженій грані. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Squaregraph.svg?width=300 |
| dbo:wikiPageExternalLink | https://dk.um.si/Dokument.php%3Fid=110389&dn= |
| dbo:wikiPageID | 20741076 (xsd:integer) |
| dbo:wikiPageLength | 5563 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094649019 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quadrilateral dbr:Algorithm dbc:Graph_families dbr:Undirected_graph dbr:Induced_subgraph dbc:Planar_graphs dbr:Mathematics dbr:Median_graph dbr:Rooted_graph dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Linear_time dbr:Chord_diagram_(mathematics) dbr:Computational_Geometry_(journal) dbr:Gear_graph dbr:Tree_(graph_theory) dbr:Triangle-free_graph dbr:Partial_cube dbr:Forbidden_graph_characterization dbr:Graph_drawing dbr:Graph_theory dbr:Claw_(graph_theory) dbr:Hamming_distance dbr:Hyperbolic_space dbr:Arrangement_of_lines dbr:Bipartite_graph dbc:Bipartite_graphs dbr:Polyomino dbr:Diameter dbr:Planar_graph dbr:Circle_graph dbr:Cartesian_product_of_graphs dbr:Simplex_graph dbr:Vertex_(graph_theory) dbr:Face_(geometry) dbr:Planarity_testing dbr:Grid_graph dbr:Bitvector dbr:Breadth_first_search dbr:Planar_dual dbr:File:Squaregraph.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_families dbc:Planar_graphs dbc:Bipartite_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, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face. (en) В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани. (ru) У теорії графів рамковим графом називають вид неорієнтованого графа, який можна намалювати на площині таким способом, що будь-яка обмежена грань є чотирикутником і будь-яка вершина з трьома і менше сусідами інцидентна необмеженій грані. (uk) En teoría de grafos, un grafo cuadrado es un grafo no dirigido que puede dibujarse en el plano de modo que cada superficie acotada es un cuadrilátero y cada vértice con tres o menos vecinos es incidente a una cara no acotada. (es) |
| rdfs:label | Grafo cuadrado (es) Squaregraph (en) Рамочный граф (ru) Рамковий граф (uk) |
| owl:sameAs | freebase:Squaregraph yago-res:Squaregraph wikidata:Squaregraph dbpedia-es:Squaregraph dbpedia-hu:Squaregraph dbpedia-ru:Squaregraph dbpedia-uk:Squaregraph https://global.dbpedia.org/id/4vQ8w |
| prov:wasDerivedFrom | wikipedia-en:Squaregraph?oldid=1094649019&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Squaregraph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Squaregraph |
| is dbo:wikiPageRedirects of | dbr:Quadrangulation |
| is dbo:wikiPageWikiLink of | dbr:List_of_graphs dbr:Penny_graph dbr:Median_graph dbr:Glossary_of_graph_theory dbr:Partial_cube dbr:King's_graph dbr:Bipartite_graph dbr:Polyomino dbr:Circle_graph dbr:Matchstick_graph dbr:Quadrangulation |
| is foaf:primaryTopic of | wikipedia-en:Squaregraph |
