In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
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. 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. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.
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. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves.
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in 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 graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G.
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak, where they called these graphs "polar graphs".
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.
In the mathematical field of graph theory, a hypergraph H is called a hypertree if it admits a host graph T such that T is a tree. In other words, H is a hypertree if there exists a tree T such that every hyperedge of H is the set of vertices of a connected subtree of T. Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.
In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.
In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.
In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques. Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs, making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics. Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.
