Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Nested_triangles_graph> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items per page.
- Nested_triangles_graph abstract "In graph theory and graph drawing, a nested triangles graph with n vertices is a planar graph formed from a sequence of n/3 triangles, by connecting pairs of corresponding vertices on consecutive triangles in the sequence. It can also be formed geometrically, by gluing together n/3 − 1 triangular prisms on their triangular faces.The nested triangles graph was named by Dolev, Leighton & Trickey (1984), who used it to show that drawing an n-vertex planar graph in the integer lattice (with straight line-segment edges) may require a bounding box of size at least n/3 × n/3. In such a drawing, no matter which face of the graph is chosen to be the outer face, some subsequence of at least n/6 of the triangles must be drawn nested within each other, and within this part of the drawing each triangle must use two rows and two columns more than the next inner triangle. Frati & Patrignani (2008) showed that this graph, and any graph formed by adding diagonals to its quadrilaterals, can be drawn within a box of dimensions n/3 × 2n/3. Although the nested triangles graph itself can be drawn in smaller area, closing the gap between this 2n2/9 upper bound and the n2/9 lower bound on drawing area for completions of the nested triangle graph remains an open problem. If the outer face is not allowed to be chosen as part of the drawing algorithm, but is specified as part of the input, the same argument shows that a bounding box of size 2n/3 × 2n/3 is necessary, and a drawing with these dimensions exists. Variants of the nested triangles graph have been used for many lower bound constructions in graph drawing, for instance on area of rectangular visibility representations, area of drawings with right angle crossings or relative area of planar versus nonplanar drawings.".
- Nested_triangles_graph thumbnail Nested_triangle_graph_18.svg?width=300.
- Nested_triangles_graph wikiPageID "39338633".
- Nested_triangles_graph wikiPageRevisionID "567150650".
- Nested_triangles_graph subject Category:Parametric_families_of_graphs.
- Nested_triangles_graph subject Category:Planar_graphs.
- Nested_triangles_graph comment "In graph theory and graph drawing, a nested triangles graph with n vertices is a planar graph formed from a sequence of n/3 triangles, by connecting pairs of corresponding vertices on consecutive triangles in the sequence.".
- Nested_triangles_graph label "Nested triangles graph".
- Nested_triangles_graph sameAs m.0v3h1_c.
- Nested_triangles_graph sameAs Q17082946.
- Nested_triangles_graph sameAs Q17082946.
- Nested_triangles_graph wasDerivedFrom Nested_triangles_graph?oldid=567150650.
- Nested_triangles_graph depiction Nested_triangle_graph_18.svg.
- Nested_triangles_graph isPrimaryTopicOf Nested_triangles_graph.
