Planar graphIn 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.
Dual graphIn the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that 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.
Outerplanar graphIn graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants. They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.
Graph embeddingIn topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Trefoil knotIn knot theory, a branch of mathematics, the trefoil knot is the simplest example of a nontrivial knot. The trefoil can be obtained by joining together the two loose ends of a common overhand knot, resulting in a knotted loop. As the simplest knot, the trefoil is fundamental to the study of mathematical knot theory. The trefoil knot is named after the three-leaf clover (or trefoil) plant. The trefoil knot can be defined as the curve obtained from the following parametric equations: The (2,3)-torus knot is also a trefoil knot.
Prime knotIn knot theory, a prime knot or prime link is a knot that is, in a certain sense, indecomposable. Specifically, it is a non-trivial knot which cannot be written as the knot sum of two non-trivial knots. Knots that are not prime are said to be composite knots or composite links. It can be a nontrivial problem to determine whether a given knot is prime or not. A family of examples of prime knots are the torus knots. These are formed by wrapping a circle around a torus p times in one direction and q times in the other, where p and q are coprime integers.
TorusIn geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanar with the circle. The main types of toruses include ring toruses, horn toruses, and spindle toruses. A ring torus is sometimes colloquially referred to as a donut or doughnut. If the axis of revolution does not touch the circle, the surface has a ring shape and is called a torus of revolution, also known as a ring torus.
Polyhedral graphIn geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs. The Schlegel diagram of a convex polyhedron represents its vertices and edges as points and line segments in the Euclidean plane, forming a subdivision of an outer convex polygon into smaller convex polygons (a convex drawing of the graph of the polyhedron).
Chiral knotIn the mathematical field of knot theory, a chiral knot is a knot that is not equivalent to its mirror image (when identical while reversed). An oriented knot that is equivalent to its mirror image is an amphicheiral knot, also called an achiral knot. The chirality of a knot is a knot invariant. A knot's chirality can be further classified depending on whether or not it is invertible. There are only five knot symmetry types, indicated by chirality and invertibility: fully chiral, invertible, positively amphicheiral noninvertible, negatively amphicheiral noninvertible, and fully amphicheiral invertible.
Linkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional 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.
Knot (mathematics)In mathematics, a knot is an embedding of the circle S^1 into three-dimensional Euclidean space, R3 (also known as E3). Often two knots are considered equivalent if they are ambient isotopic, that is, if there exists a continuous deformation of R3 which takes one knot to the other. 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.
Planar separator theoremIn graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(\sqrt{n}) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
Knot theoryIn topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be undone, the simplest knot being a ring (or "unknot"). In mathematical language, a knot is an embedding of a circle in 3-dimensional Euclidean space, . Two mathematical knots are equivalent if one can be transformed into the other via a deformation of upon itself (known as an ambient isotopy); these transformations correspond to manipulations of a knotted string that do not involve cutting it or passing it through itself.
Planarity testingIn graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal.
Topological graph theoryIn mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three utilities problem.
Toroidal graphIn the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. Any graph that can be embedded in a plane can also be embedded in a torus. A toroidal graph of genus 1 can be embedded in a torus but not in a plane. The Heawood graph, the complete graph K7 (and hence K5 and K6), the Petersen graph (and hence the complete bipartite graph K3,3, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks, and all Möbius ladders are toroidal.
Link (knot theory)In mathematical knot theory, a link is a collection of knots which do not intersect, but which may be linked (or knotted) together. A knot can be described as a link with one component. Links and knots are studied in a branch of mathematics called knot theory. Implicit in this definition is that there is a trivial reference link, usually called the unlink, but the word is also sometimes used in context where there is no notion of a trivial link.
Cubic graphIn the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph. In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.
Knot complementIn mathematics, the knot complement of a tame knot K is the space where the knot is not. If a knot is embedded in the 3-sphere, then the complement is the 3-sphere minus the space near the knot. To make this precise, suppose that K is a knot in a three-manifold M (most often, M is the 3-sphere). Let N be a tubular neighborhood of K; so N is a solid torus. The knot complement is then the complement of N, The knot complement XK is a compact 3-manifold; the boundary of XK and the boundary of the neighborhood N are homeomorphic to a two-torus.
Figure-eight knot (mathematics)In knot theory, a figure-eight knot (also called Listing's knot) is the unique knot with a crossing number of four. This makes it the knot with the third-smallest possible crossing number, after the unknot and the trefoil knot. The figure-eight knot is a prime knot. The name is given because tying a normal figure-eight knot in a rope and then joining the ends together, in the most natural way, gives a model of the mathematical knot.
