100 relations: Algorithm, Apex graph, Apollonian network, Big O notation, Branch-decomposition, Butterfly graph, Chordal graph, Circle packing theorem, Circuit rank, Clique-sum, Colin de Verdière graph invariant, Combinatorial map, Complete bipartite graph, Complete graph, Connectivity (graph theory), Convex polygon, Convex polytope, Cycle (graph theory), Cycle space, David Bader (computer scientist), Dense graph, Directed acyclic graph, Dual graph, Equivalence class, Euler characteristic, Fáry's theorem, Forbidden graph characterization, Four color theorem, Genus (mathematics), Geometric graph theory, Glossary of graph theory terms, Graph (discrete mathematics), Graph coloring, Graph embedding, Graph isomorphism problem, Graph minor, Graph theory, Halin graph, Hanani–Tutte theorem, Homeomorphism, Homeomorphism (graph theory), If and only if, Integer lattice, Intersection graph, Isomorphism, Journal of Graph Algorithms and Applications, K-tree, K-vertex-connected graph, Kazimierz Kuratowski, Klaus Wagner, ..., Kuratowski's theorem, Left-right planarity test, Line (geometry), Line graph, Line segment, Linking number, Linkless embedding, Mac Lane's planarity criterion, Map graph, Mathematical induction, Meshedness coefficient, Order (journal), Order dimension, Osculating circle, Outerplanar graph, Paul Koebe, Peripheral cycle, Perspective (graphical), Petersen family, Planar separator theorem, Planarity, Planarity testing, Planarization, Plane (geometry), Plane curve, Poland, Polyhedral graph, Regular polygon, Robertson–Seymour theorem, Scheinerman's conjecture, Schlegel diagram, Schnyder's theorem, Simple polygon, Sphere, Sprouts (game), Steinitz's theorem, Stereographic projection, Strangulated graph, Thickness (graph theory), Three utilities problem, Topological conjugacy, Toroidal graph, Torus, Tree (graph theory), Treewidth, Universal point set, Upward planar drawing, Wagner's theorem, Whitney's planarity criterion, 1-planar graph. Expand index (50 more) » « Shrink index
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles.
Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves.
In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar undirected graph with 5 vertices and 6 edges.
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint.
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest.
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology.
Colin de Verdière's invariant is a graph parameter \mu(G) for any graph G, introduced by Yves Colin de Verdière in 1990.
A combinatorial map is a combinatorial object modelling topological structures with subdivided objects.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.
A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon.
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn.
In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its Eulerian subgraphs.
David A. Bader (born May 4, 1969) is a Professor, Chair of the School of Computational Science and Engineering, and Executive Director of High-Performance Computing in the Georgia Tech College of Computing.
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges.
In mathematics and computer science, a directed acyclic graph (DAG), is a finite directed graph with no directed cycles.
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of.
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation) defined on them, then one may naturally split the set S into equivalence classes.
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent.
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.
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
In mathematics, genus (plural genera) has a few different, but closely related, meanings.
A geometric graph is a graph in which the vertices or edges are associated with geometric objects, the simplest realisation is a Random geometric graph.
This is a glossary of graph theory terms.
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".
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of) are associated with edges in such a way that.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.
In topological graph theory, the Hanani–Tutte theorem is a result on the parity of edge crossings in a graph drawing.
In the mathematical field of topology, a homeomorphism or topological isomorphism or bi continuous function is a continuous function between topological spaces that has a continuous inverse function.
In graph theory, two graphs G and G' are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of G'.
In logic and related fields such as mathematics and philosophy, if and only if (shortened iff) is a biconditional logical connective between statements.
In mathematics, the n-dimensional integer lattice (or cubic lattice), denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are ''n''-tuples of integers.
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets.
In mathematics, an isomorphism (from the Ancient Greek: ἴσος isos "equal", and μορφή morphe "form" or "shape") is a homomorphism or morphism (i.e. a mathematical mapping) that can be reversed by an inverse morphism.
The Journal of Graph Algorithms and Applications is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing.
In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that, together, the k + 1 vertices form a clique.
In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.
Kazimierz Kuratowski (Polish pronunciation:, 2 February 1896 – 18 June 1980) was a Polish mathematician and logician.
Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician.
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski.
In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm.
The notion of line or straight line was introduced by ancient mathematicians to represent straight objects (i.e., having no curvature) with negligible width and depth.
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.
In geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its endpoints.
In mathematics, the linking number is a numerical invariant that describes the linking of two closed curves in three-dimensional space.
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.
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.
In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane.
Mathematical induction is a mathematical proof technique.
In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices.
Order (subtitled "A Journal on the Theory of Ordered Sets and its Applications") is a quarterly peer-reviewed academic journal on order theory and its applications, published by Springer Science+Business Media.
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.
In differential geometry of curves, the osculating circle of a sufficiently smooth plane curve at a given point p on the curve has been traditionally defined as the circle passing through p and a pair of additional points on the curve infinitesimally close to p. Its center lies on the inner normal line, and its curvature is the same as that of the given curve at that point.
In 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.
Paul Koebe (15 February 1882 – 6 August 1945) was a 20th-century German mathematician.
In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part.
Perspective (from perspicere "to see through") in the graphic arts is an approximate representation, generally on a flat surface (such as paper), of an image as it is seen by the eye.
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6.
In 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.
Planarity is a puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University.
In 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).
In graph drawing, planarization is a method of extending drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.
In mathematics, a plane is a flat, two-dimensional surface that extends infinitely far.
In mathematics, a plane curve is a curve in a plane that may be either a Euclidean plane, an affine plane or a projective plane.
Poland (Polska), officially the Republic of Poland (Rzeczpospolita Polska), is a country located in Central Europe.
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron.
In Euclidean geometry, a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).
In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.
In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane.
In geometry, a Schlegel diagram is a projection of a polytope from R^d into R^ through a point beyond one of its facets or faces.
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets.
In geometry a simple polygon is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pair-wise to form a closed path.
A sphere (from Greek σφαῖρα — sphaira, "globe, ball") is a perfectly round geometrical object in three-dimensional space that is the surface of a completely round ball (viz., analogous to the circular objects in two dimensions, where a "circle" circumscribes its "disk").
Sprouts is a paper-and-pencil game with significant mathematical properties.
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the (simple) 3-vertex-connected planar graphs (with at least four vertices).
In geometry, the stereographic projection is a particular mapping (function) that projects a sphere onto a plane.
In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph.
In graph theory, the thickness of a graph is the minimum number of planar graphs into which the edges of can be partitioned.
The classical mathematical puzzle known as the three utilities problem; the three cottages problem or sometimes water, gas and electricity can be stated as follows: The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation.
In mathematics, two functions are said to be topologically conjugate to one another if there exists a homeomorphism that will conjugate the one into the other.
In mathematics, a toroidal graph is a graph that can be embedded on a torus.
In geometry, a torus (plural tori) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis coplanar with the circle.
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
In graph theory, the treewidth of an undirected graph is a number associated with the graph.
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 straight-line drawing in which the vertices are all placed at points of S.
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.
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).
In mathematics, Whitney's planarity criterion is a matroid-theoretic characterization of planar graphs, named after Hassler Whitney.
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.
Convex plane graph, Kuratowski's reduction theorem, Maximal planar graph, Nonplanar graph, Outer planar graph, Outplanar graph, Planar Graph, Planar embedding, Planar embedding of the graph, Planar graphs, Planar map, Planarity (graph theory), Plane graph, Planer graph, Pontryagin-Kuratowski theorem, Pontryagin–Kuratowski theorem, Theorem P, Triangular graph, Wagner theorem.