Circular-arc graphIn graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where and A family of arcs that corresponds to G is called an arc model. demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in time.
Unit disk graphIn geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other. They are commonly formed from a Poisson point process, making them a simple example of a random structure.
Line–line intersectionIn Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or another line. Distinguishing these cases and finding the intersection have uses, for example, in computer graphics, motion planning, and collision detection. In three-dimensional Euclidean geometry, if two lines are not in the same plane, they have no point of intersection and are called skew lines.
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).
Total coloringIn graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ′′(G) of a graph G is the fewest colors needed in any total coloring of G.
Simple groupIn mathematics, a simple group is a nontrivial group whose only normal subgroups are the trivial group and the group itself. A group that is not simple can be broken into two smaller groups, namely a nontrivial normal subgroup and the corresponding quotient group. This process can be repeated, and for finite groups one eventually arrives at uniquely determined simple groups, by the Jordan–Hölder theorem. The complete classification of finite simple groups, completed in 2004, is a major milestone in the history of mathematics.
Line segmentIn geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints. In geometry, a line segment is often denoted using a line above the symbols for the two endpoints (such as ).
Line (geometry)In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are one-dimensional objects, though they may exist embedded in two, three, or higher dimensional spaces. The word line may also refer to a line segment in everyday life that has two points to denote its ends (endpoints). A line can be referred to by two points that lie on it (e.g. ) or by a single letter (e.g. ).
Feedback arc setIn graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used.
Intersection theoryIn mathematics, intersection theory is one of the main branches of algebraic geometry, where it gives information about the intersection of two subvarieties of a given variety. The theory for varieties is older, with roots in Bézout's theorem on curves and elimination theory. On the other hand, the topological theory more quickly reached a definitive form. There is yet an ongoing development of intersection theory. Currently the main focus is on: virtual fundamental cycles, quantum intersection rings, Gromov-Witten theory and the extension of intersection theory from schemes to stacks.
