|
Area (graph Drawing)
In graph drawing, the area used by a drawing is a commonly used way of measuring its quality. Definition For a drawing style in which the vertices are placed on the integer lattice, the area of the drawing may be defined as the area of the smallest axis-aligned bounding box of the drawing: that is, it the product of the largest difference in ''x''-coordinates of two vertices with the largest difference in ''y''-coordinates. For other drawing styles, in which vertices are placed more freely, the drawing may be scaled so that the closest pair of vertices have distance one from each other, after which the area can again be defined as the area of a smallest bounding box of a drawing. Alternatively, the area can be defined as the area of the convex hull of the drawing, again after appropriate scaling.. Polynomial bounds For straight-line drawings of planar graphs with ''n'' vertices, the optimal worst-case bound on the area of a drawing is Θ(''n''2). The nested triangles graph requ ... [...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] |
Crossing Number (graph Theory)
In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph . For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing. The study of crossing numbers originated in Turán's brick factory problem, in which Pál Turán asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a complete bipartite graph. The same problem arose independently in sociology at approximately the same time, in connection with the construction of sociograms. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Order
In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Instead, a cyclic order is defined as a ternary relation , meaning "after , one reaches before ". For example, une, October, February but not une, February, October cf. picture. A ternary relation is called a cyclic order if it is cyclic, asymmetric, transitive, and connected. Dropping the "connected" requirement results in a partial cyclic order. A set with a cyclic order is called a cyclically ordered set or simply a cycle. Some familiar cycles are discrete, having only a finite number of elements: there are seven days of the week, four cardinal directions, twelve notes in the chromatic scale, and three plays in rock-paper-scissors. In a finite cycle, each element has a "next element" and a "previous element". There are also continu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree (graph Theory)
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''at most one'' path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A polytreeSee . (or directed tree or oriented treeSee .See . or singly connected networkSee .) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree, either making all its edges point away from the root—in which case it is called ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete And Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry. Abstracting and indexing The journal is indexed in: * ''Mathematical Reviews'' * ''Zentralblatt MATH'' * ''Science Citation Index'' * ''Current Contents''/Engineering, Computing and Technology Notable articles The articles by Gil Kalai with a proof of a subexponential upper bound on the diameter of a polyhedron and by Samuel Ferguson on the Kepler conjecture, both published in Discrete & Computational geometry, earned their author the Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e .... References External links ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Directed Acyclic Graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling). Directed acyclic graphs are sometimes instead called acyclic directed graphs or acyclic digraphs. Definitions A graph is formed by vertices and by edges connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a directed graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Upward Planar Drawing
In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized. Characterizations A directed acyclic graph must be planar in order to have an upward planar drawing, but not every planar acyclic graph has such a drawing. Among the planar directed acyclic graphs with a single source (vertex with no incoming edges) and sink (vertex with no outgoing edges), the graphs with upward planar drawings are the ''st''-planar graphs, planar graphs in which the source and sink both belo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exponential Growth
Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a quantity undergoing exponential growth is an exponential function of time, that is, the variable representing time is the exponent (in contrast to other types of growth, such as quadratic growth). If the constant of proportionality is negative, then the quantity decreases over time, and is said to be undergoing exponential decay instead. In the case of a discrete domain of definition with equal intervals, it is also called geometric growth or geometric decay since the function values form a geometric progression. The formula for exponential growth of a variable at the growth rate , as time goes on in discrete intervals (that is, at integer times 0, 1, 2, 3, ...), is x_t = x_0(1+r)^t where is the value of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polyline
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments connecting the consecutive vertices. Name A polygonal chain may also be called a polygonal curve, polygonal path, polyline,. piecewise linear curve, broken line or, in geographic information systems, a linestring or linear ring. Variations A simple polygonal chain is one in which only consecutive (or the first and the last) segments intersect and only at their endpoints. A closed polygonal chain is one in which the first vertex coincides with the last one, or, alternatively, the first and the last vertices are also connected by a line segment. A simple closed polygonal chain in the plane is the boundary of a simple polygon. Often the term "polygon" is used in the meaning of "closed polygonal chain", but in some cases it is important to d ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Series–parallel Graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and terminology In this context, the term graph means multigraph. There are several ways to define series–parallel graphs. The following definition basically follows the one used by David Eppstein. A two-terminal graph (TTG) is a graph with two distinguished vertices, ''s'' and ''t'' called ''source'' and ''sink'', respectively. The parallel composition ''Pc = Pc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y'' by merging the sources of ''X'' and ''Y'' to create the source of ''Pc'' and merging the sinks of ''X'' and ''Y'' to create the sink of ''Pc''. The series composition ''Sc = Sc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
International Symposium On Graph Drawing
The International Symposium on Graph Drawing (GD) is an annual academic conference in which researchers present peer reviewed papers on graph drawing, information visualization of network information, geometric graph theory, and related topics. Significance The Graph Drawing symposia have been central to the growth and development of graph drawing as a research area: as Herman et al. write, "the Graph Drawing community grew around the yearly Symposia." Nguyen lists Graph Drawing as one of "several good conferences which directly or indirectly concern with information visualization", and Wong et al. report that its proceedings "provide a wealth of information". In a 2003 study the symposium was among the top 30% of computer science research publication venues, ranked by impact factor. History The first symposium was held in Marino, near Rome, Italy, in 1992, organized by Giuseppe Di Battista, Peter Eades, Pierre Rosenstiehl, and Roberto Tamassia. The first two symposia did not ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bend Minimization
In graph drawing styles that represent the edges of a graph by polylines (sequences of line segments connected at bends), it is desirable to minimize the number of bends per edge (sometimes called the curve complexity). or the total number of bends in a drawing.. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities. Eliminating all bends The prototypical example of bend minimization is Fáry's theorem, which states that every planar graph can be drawn with no bends, that is, with all its edges drawn as straight line segments. Drawings of a graph in which the edges are both bendless and axis-aligned are sometimes called ''rectilinear drawings'', and are one way of constructing RAC drawings in which all crossings are at right angles. However, it is NP-complete to determine whether a planar graph has a planar rectilinear drawing, and NP-complete to determine whether an arbitrary graph has a rectilinear drawing that allows crossings.. Bend ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
