Geometric graph theory

The geometric graph theory is a special branch of graph theory that deals with the study of geometric graphs. A geometric graph is a graph, associated with the nodes or edges of the geometric object or configurations. Following graphs and problems of geometric graph theory are known:

• A planar graph is a line graph in which the nodes as points in the Euclidean plane and the edges are embedded as non- overlapping line segments. The set of Fary says that every planar graph has a representation as a planar graph distance. A triangulation line graph is a plane to which no edges can be added. A special case is the Delaunay triangulation - a graph of results from a set of points in the plane, by always connecting two points with one edge, as soon as there is a circle containing only these two points.

• 1 the framework of a polyhedron, or polytope, the amount of nodes and edges of the polytope. The skeleton of a convex polyhedron is always a planar graph, and the skeleton of a k-dimensional convex polytope is always a k -fold node connected graph. Conversely, the set of Steinitz says that every 3-connected planar graph is the skeleton of a convex polyhedron. Therefore the graph of this class are referred to as Polyedergraphen.

• A Euclidean graph is a graph in which the nodes are represented by points in the plane, and in which the edge is associated with the Euclidean distance between these points. The Euclidean minimum spanning tree is the minimum spanning tree of a Euclidean complete graph. It is also possible to define the graph based on distance conditions. In particular, it forms a unit distance graph by connecting distant points equal to each other. The Hadwiger -Nelson problem deals with the chromatic number of these graphs.

• An average graph is a graph in which each node is associated with an amount and at the nodes connected by edges, when the respective sets form a non- empty intersection. If the quantities geometric objects, the result obtained is a geometric graph. For example, the section of the graph of straight lines in the first dimension to an interval graph, and the graph of cut sheets in the plane a unit disk graph unit. The circle packing theorem states that the average graphs of non- intersecting circles are exactly the planar graphs. The Scheiner man 's conjecture says that every planar graph can be represented as the intersection graph of straight line segments in the plane.

• A Levi graph of a family of points and lines has a node for each of these objects and an edge for each incident with point - line pair. Levi graphs of projective configurations lead to many important symmetric graphs and cages.

• The visibility graph of a closed polygon connects a pair of nodes with an edge if the corresponding line segment is completely contained in the polygon. So far, no efficient test is known whether an undirected graph can be represented by a visibility graph.

• A partial cube is a graph in which the nodes are associated with the nodes in a hypercube, in such a manner that the distances in the graph correspond to the Hamming distance between the corresponding node hypercube. Many important families of combinatorial structures such as the acyclic orientations of a graph or the adjacency between regions in a hyperplane arrangement can be represented as a partial cube graph. An important special case of a partial cube is the skeleton of an Permutoeders. This is a graph in which nodes permutations of a set of ordered objects and edges represent substitutions of successive objects. Many other important classes of graphs including median graphs have related definitions that require metric embeddings.

• A flip- graph formed by the triangulations of a point set, in which each node represents a triangulation and two triangulations are connected with an edge if they differ from each other by the displacement of an edge. It is also possible to define similar flip- graph for subdivisions into squares or pseudo- triangles, and for higher-dimensional triangulations. The flip graph of triangulations of a convex polygon forming the skeleton of the Associaeders (or Stasheff polytope ). The flip- graph of regular triangulations of a point set (projections of higher-dimensional convex envelopes) can also be represented as a framework of the so-called Sekundärpolytop.