Geometric graph theory
The geometric graph theory is a special branch of graph theory , which deals with the investigation of geometric graphs. A geometric graph is a graph in which nodes or edges are linked to geometric objects or configurations . With the geometric graph theory closely related is the topological graph theory .
The following graphs and problems of geometric graph theory are known:
- A plane line graph is a graph that has a straight line representation in the Euclidean plane . The Wagner and Fáry theorem states that every planar graph can be realized as a plane segment graph . A triangulation is a plane line graph to which no edges can be added. A special case is the Delaunay triangulation - a graph that arises from a set of points in the plane by connecting two points with an edge whenever a circle exists that contains only these two points.
- The 1-framework of a polyhedron or polytope is the set of nodes and edges of the polytope. The framework of a convex polyhedron is always a planar graph, and the framework of a k -dimensional convex polytope is always a k -fold vertex-connected graph ( Balinski's theorem ). Conversely, Steinitz's theorem says that every 3-connected planar graph is the framework of a convex polyhedron. Therefore, graphs of this class are also called polyhedron graphs .
- A Euclidean graph is a graph in which the nodes are represented by points in the plane, and in which the edges are assigned the Euclidean distance between these points. The Euclidean minimal spanning tree is the minimal spanning tree of a Euclidean complete graph . It is also possible to define graphs based on distance conditions. In particular, one forms a unit distance graph by connecting equidistant points. The Hadwiger-Nelson problem deals with the chromatic number of these graphs.
- An intersection graph is a graph in which each node is associated with a set and where nodes are connected by edges when the corresponding sets form a non-empty intersection. If the sets are geometric objects, the result is a geometric graph. For example, the intersection graph of straight line segments in the first dimension is an interval graph and the intersection graph of unit slices in the plane is a unit slice graph . The circle packing theorem says that the intersection graphs of non-intersecting circles are exactly the planar graphs. The Scheinermann conjecture says that every planar graph can be represented as an intersection graph of straight lines 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 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 for 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 of a hypercube in such a way that the distances in the graph match the Hamming distances between the corresponding hypercube nodes. Many important families of combinatorial structures, such as the acyclic orientations of a graph or the neighborhood between regions in a hyperplane arrangement , can be represented as partial cube graphs . An important special case of a partial cube is the framework of a permutahedron . This is a graph in which nodes represent permutations of a set of ordered objects and edges represent interchanges of successive objects. Many other important graph classes, including median graphs , have related definitions that require metric embeddings.
- A flip graph is formed from the triangulations of a point set, in which each node represents a triangulation and two triangulations are connected to an edge if they differ from one another by the offset of an edge. It is also possible to define similar flip graphs for subdivisions into quadrangles or pseudo-triangles , and for higher-dimensional triangulations. The flip-graph of triangulations of a convex polygon forms the framework of the associaedron (or Stasheff polytope). The flip graph of regular triangulations of a point set (projections of higher-dimensional convex hulls) can also be represented as a framework by the so-called secondary polytope.
- In a random geometric graph , the nodes are evenly distributed over the underlying space and are connected precisely when their distance is less than a previously specified parameter.
See also
literature
- Hans-Jürgen Bandelt, Victor Chepoi: Metric graph theory and geometry: a survey . In: Contemp. Math. 2008 ( online [PDF; 377 kB ]).
- János Pach : Towards a Theory of Geometric Graphs . Contemporary Mathematics, no.342, American Mathematical Society, 2004.
- Tomaž Pisanski , Milan Randić : Bridges between geometry and graph theory . In: CA Gorini (ed.): Geometry at Work: Papers in Applied Geometry . Mathematical Association of America, Washington, DC 2000, pp. 174–194 ( online [PDF; 704 kB ]).
Individual evidence
- ↑ Harv, Bandelt and Chepoi., 2008