WikiMili The Free Encyclopedia

A **three-dimensional graph** may refer to

- A graph (discrete mathematics), embedded into a three-dimensional space
- The graph of a function of two variables, embedded into a three-dimensional space

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

disambiguation page lists mathematics articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article. | This

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In the mathematical field of graph theory, a **complete graph** is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A **complete digraph** is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

High-dimensional data, meaning data that requires more than two or three dimensions to represent, can be difficult to interpret. One approach to simplification is to assume that the data of interest lie on an embedded non-linear manifold within the higher-dimensional space. If the manifold is of low enough dimension, the data can be visualised in the low-dimensional space.

In mathematics, a **knot** is an embedding of a circle *S*^{1} in 3-dimensional Euclidean space, **R**^{3}, considered up to continuous deformations (isotopies). A crucial difference between the standard mathematical and conventional notions of a knot is that mathematical knots are closed—there are no ends to tie or untie on a mathematical knot. Physical properties such as friction and thickness also do not apply, although there are mathematical definitions of a knot that take such properties into account. The term *knot* is also applied to embeddings of *S*^{ j} in *S*^{n}, especially in the case *j* = *n* − 2. The branch of mathematics that studies knots is known as knot theory, and has many simple relations to graph theory.

In topological graph theory, a mathematical discipline, a **linkless embedding** of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked. A **flat embedding** is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A **linklessly embeddable graph** is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an **intrinsically linked graph** is a graph that does not have a linkless embedding.

In graph theory, **Mac Lane's planarity criterion** is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if
the cycle space of the graph has a cycle basis in which each edge of the graph participates in at most two basis vectors.

In mathematics, topology generalizes the notion of triangulation in a natural way as follows:

In the mathematical discipline of graph theory, the **dual graph** of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a **book embedding** is a generalization of planar embedding of a graph to embeddings into a *book*, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the *spine*, and the edges are required to stay within a single half-plane. The **book thickness** of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called **pagenumber**, **stacknumber** or **fixed outerthickness**. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In mathematics, **Fáry's theorem** states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

In mathematics, and particularly geometric graph theory, a **unit distance graph** is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. Edges of unit distance graphs sometimes cross each other, so they are not always planar; a unit distance graph without crossings is called a **matchstick graph**.

In graph theory, a connected graph *G* is said to be ** k-vertex-connected** if it has more than

In topological graph theory, an **embedding** of a graph
on a surface
is a representation of
on
in which points of
are associated with vertices and simple arcs are associated with edges in such a way that:

**Isomap** is a nonlinear dimensionality reduction method. It is one of several widely used low-dimensional embedding methods. Isomap is used for computing a quasi-isometric, low-dimensional embedding of a set of high-dimensional data points. The algorithm provides a simple method for estimating the intrinsic geometry of a data manifold based on a rough estimate of each data point’s neighbors on the manifold. Isomap is highly efficient and generally applicable to a broad range of data sources and dimensionalities.

**Two-dimensional space** is a geometric setting in which two values are required to determine the position of an element. In Mathematics, it is commonly represented by the symbol ℝ^{2}. For a generalization of the concept, see dimension.

In graph theory, a branch of mathematics, a **crown graph** on 2*n* vertices is an undirected graph with two sets of vertices {*u*_{1}, *u*_{2}, ..., *u*_{n}} and {*v*_{1}, *v*_{2}, ..., *v*_{n}} and with an edge from *u*_{i} to *v*_{j} whenever *i* ≠ *j*.

In graph theory, the **Petersen family** is a set of seven undirected graphs that includes the Petersen graph and the complete graph *K*_{6}. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.

In graph theory, a **partial cube** is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a *Hamming labeling*; it represents an isometric embedding of the partial cube into a hypercube.

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 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 (1963), 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.

In distributed computing and geometric graph theory, **greedy embedding** is a process of assigning coordinates to the nodes of a telecommunications network in order to allow greedy geographic routing to be used to route messages within the network. Although greedy embedding has been proposed for use in wireless sensor networks, in which the nodes already have positions in physical space, these existing positions may differ from the positions given to them by greedy embedding, which may in some cases be points in a virtual space of a higher dimension, or in a non-Euclidean geometry. In this sense, greedy embedding may be viewed as a form of graph drawing, in which an abstract graph is embedded into a geometric space.