Edge coloringIn graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.
QuadrilateralIn geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words quadri, a variant of four, and latus, meaning "side". It is also called a tetragon, derived from greek "tetra" meaning "four" and "gon" meaning "corner" or "angle", in analogy to other polygons (e.g. pentagon). Since "gon" means "angle", it is analogously called a quadrangle, or 4-angle. A quadrilateral with vertices , , and is sometimes denoted as .
CircleA circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. The distance between any point of the circle and the centre is called the radius. Usually, the radius is required to be a positive number. A circle with (a single point) is a degenerate case. This article is about circles in Euclidean geometry, and, in particular, the Euclidean plane, except where otherwise noted. Specifically, a circle is a simple closed curve that divides the plane into two regions: an interior and an exterior.
Line graphIn 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. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.
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.
Cyclic quadrilateralIn Euclidean geometry, a cyclic quadrilateral or inscribed quadrilateral is a quadrilateral whose vertices all lie on a single circle. This circle is called the circumcircle or circumscribed circle, and the vertices are said to be concyclic. The center of the circle and its radius are called the circumcenter and the circumradius respectively. Other names for these quadrilaterals are concyclic quadrilateral and chordal quadrilateral, the latter since the sides of the quadrilateral are chords of the circumcircle.
Tangential quadrilateralIn Euclidean geometry, a tangential quadrilateral (sometimes just tangent quadrilateral) or circumscribed quadrilateral is a convex quadrilateral whose sides all can be tangent to a single circle within the quadrilateral. This circle is called the incircle of the quadrilateral or its inscribed circle, its center is the incenter and its radius is called the inradius. Since these quadrilaterals can be drawn surrounding or circumscribing their incircles, they have also been called circumscribable quadrilaterals, circumscribing quadrilaterals, and circumscriptible quadrilaterals.
List of graphsThis partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.
Ex-tangential quadrilateralIn Euclidean geometry, an ex-tangential quadrilateral is a convex quadrilateral where the extensions of all four sides are tangent to a circle outside the quadrilateral. It has also been called an exscriptible quadrilateral. The circle is called its excircle, its radius the exradius and its center the excenter (E in the figure). The excenter lies at the intersection of six angle bisectors.
Edge (geometry)In geometry, an edge is a particular type of line segment joining two vertices in a polygon, polyhedron, or higher-dimensional polytope. In a polygon, an edge is a line segment on the boundary, and is often called a polygon side. In a polyhedron or more generally a polytope, an edge is a line segment where two faces (or polyhedron sides) meet. A segment joining two vertices while passing through the interior or exterior is not an edge but instead is called a diagonal.
Graph isomorphismIn graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as . In the case when the bijection is a mapping of a graph onto itself, i.
Petersen graphIn the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by .
Chordal graphIn 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. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.
Apollonian circlesIn geometry, Apollonian circles are two families (pencils) of circles such that every circle in the first family intersects every circle in the second family orthogonally, and vice versa. These circles form the basis for bipolar coordinates. They were discovered by Apollonius of Perga, a renowned Greek geometer. The Apollonian circles are defined in two different ways by a line segment denoted CD.
Geometric graph theoryGeometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013).
Bipartite graphIn the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.
Graph operationsIn the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations create a new graph from a single initial graph. Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc.
Circles of ApolloniusThe circles of Apollonius are any of several sets of circles associated with Apollonius of Perga, a renowned Greek geometer. Most of these circles are found in planar Euclidean geometry, but analogs have been defined on other surfaces; for example, counterparts on the surface of a sphere can be defined through stereographic projection. The main uses of this term are fivefold: Apollonius showed that a circle can be defined as the set of points in a plane that have a specified ratio of distances to two fixed points, known as foci.
Bicentric quadrilateralIn Euclidean geometry, a bicentric quadrilateral is a convex quadrilateral that has both an incircle and a circumcircle. The radii and centers of these circles are called inradius and circumradius, and incenter and circumcenter respectively. From the definition it follows that bicentric quadrilaterals have all the properties of both tangential quadrilaterals and cyclic quadrilaterals. Other names for these quadrilaterals are chord-tangent quadrilateral and inscribed and circumscribed quadrilateral.
Twin circlesIn geometry, the twin circles are two special circles associated with an arbelos. An arbelos is determined by three collinear points A, B, and C, and is the curvilinear triangular region between the three semicircles that have AB, BC, and AC as their diameters. If the arbelos is partitioned into two smaller regions by a line segment through the middle point of A, B, and C, perpendicular to line ABC, then each of the two twin circles lies within one of these two regions, tangent to its two semicircular sides and to the splitting segment.
