|
Universal Point Set
In graph drawing, a universal point set of order ''n'' is a set ''S'' of points in the Euclidean plane with the property that every ''n''-vertex planar graph has a Fáry's theorem, straight-line drawing in which the vertices are all placed at points of ''S''. Bounds on the size of universal point sets When ''n'' is ten or less, there exist universal point sets with exactly ''n'' points, but for all ''n'' ≥ 15 additional points are required. Several authors have shown that subsets of the integer lattice of size ''O''(''n'') × ''O''(''n'') are universal. In particular, showed that a grid of (2''n'' − 3) × (''n'' − 1) points is universal, and reduced this to a triangular subset of an (''n'' − 1) × (''n'' − 1) grid, with ''n''2/2 − ''O''(''n'') points. By modifying the method of de Fraysseix et al., found an embedding of any planar graph into ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics. A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph., p. 6. In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and aesthetics. The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map. Graphical conventions Graphs are frequently drawn as node–lin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
