# Geometric graph theory

In

mathematics , a**geometric graph**is a graph in which the vertices or edges are associated with geometric objects or configurations.**Geometric graph theory**is a specialization ofgraph theory that studies geometric graphs. Notable geometric graphs and geometric graph theory problems include the following.* A "

planar straight line graph " is a graph in which the vertices are embedded as points in theEuclidean plane , and the edges are embedded as non-crossingline segment s.Fáry's theorem states that anyplanar graph may be represented as a planar straight line graph. A triangulation is a planar straight line graph to which no more edges may be added; a special case of this is theDelaunay triangulation , a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points.* The 1-skeleton of a

polyhedron orpolytope is the set of vertices and edges of the polytope. The skeleton of any convex polyhedron is a planar graph, and the skeleton of any "k"-dimensional convex polytope is a "k"-connected graph. Conversely,Ernst Steinitz proved that any 3-connected planar graph is the skeleton of a convex polyhedron.* A "Euclidean graph" is a graph in which the vertices represent points in the plane, and the edges are assigned lengths equal to the Euclidean distance between those points. The

Euclidean minimum spanning tree is theminimum spanning tree of a Euclideancomplete graph . It is also possible to define graphs by conditions on the distances; in particular, aunit distance graph is formed by connecting pairs of points that are a unit distance apart in the plane. TheHadwiger–Nelson problem concerns thechromatic number of these graphs.* An

intersection graph is a graph in which each vertex is associated with a set and in which vertices are connected by edges whenever the corresponding sets have a nonempty intersection. When the sets are geometric objects, the result is a geometric graph. For instance, the intersection graph of line segments in one dimension is aninterval graph ; the intersection graph of unit disks in the plane is aunit disk graph . TheCircle packing theorem states that the intersection graphs of non-crossing circles are exactly the planar graphs.Scheinerman's conjecture states that every planar graph can be represented as the intersection graph of line segments in the plane.* A

Levi graph of a family of points and lines has a vertex for each of these objects and an edge for every incident point-line pair. The Levi graphs ofprojective configuration s lead to many importantsymmetric graph s and cages.* The

visibility graph of a closed polygon connects each pair of vertices by an edge whenever the line segment connecting the vertices lies entirely in the polygon. It is not known how to test efficiently whether an undirected graph can be represented as a visibility graph.* A

partial cube is a graph for which the vertices can be associated with the vertices of ahypercube , in such a way that distance in the graph equalsHamming distance between the corresponding hypercube vertices. Many important families of combinatorial structures, such as the acyclic orientations of a graph or the adjacencies between regions in ahyperplane arrangement , can be represented as partial cube graphs. An important special case of a partial cube is the skeleton of the permutohedron, a graph in which vertices represent permutations of a set of ordered objects and edges represent swaps of objects adjacent in the order. Several other important classes of graphs includingmedian graph s have related definitions involving metric embeddings Harv|Bandelt|Chepoi|2008|Ref=none.* A

flip graph is a graph formed from the triangulations of a point set, in which each vertex represents a triangulation and two triangulations are connected by an edge if they differ by the replacement of one edge for another. It is also possible to define related flip graphs for partitions into quadrilaterals or pseudotriangles, and for higher dimensional triangulations. The flip graph of triangulations of a convex polygon forms the skeleton of theassociahedron orStasheff polytope . The flip graph ofregular triangulation s of a point set (projections of higher dimensional convex hulls) can also be represented as a skeleton, of the so-called "secondary polytope".**See also***

Topological graph theory **References***cite journal

last= Bandelt

first= Hans-Jürgen

coauthors= Chepoi, Victor

url = http://www.lif-sud.univ-mrs.fr/%7Echepoi/survey_cm_bis.pdf

format= PDF

title = Metric graph theory and geometry: a survey

journal = Contemp. Math.

year= 2008

pages = to appear*cite book

author = Pach, János, ed.

title = Towards a Theory of Geometric Graphs

year = 2004

publisher = Contemporary Mathematics, no. 342, American Mathematical Society*cite conference

author = Pisanski, Tomaž; Randić, Milan

title = Bridges between geometry and graph theory

date = 2000

url = http://www.ijp.si/ftp/pub/preprints/ps/98/pp595.ps

booktitle = Geometry at Work: Papers in Applied Geometry

editor = Gorini, C. A. (Ed.)

location = Washington, DC

publisher = Mathematical Association of America

pages = 174–194

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Geometric group theory**— is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… … Wikipedia**Graph theory**— In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia**Algebraic graph theory**— is a branch of mathematics in which algebraic methods are applied to problems about graphs. In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the… … Wikipedia**Vertex (graph theory)**— For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… … Wikipedia**Topological graph theory**— In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, and graphs as topological spaces. [J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987] Embedding a… … Wikipedia**Cut (graph theory)**— In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are… … Wikipedia**Glossary of graph theory**— Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia**Crossing number (graph theory)**— A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… … Wikipedia**Independent set (graph theory)**— The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices … Wikipedia**Random geometric graph**— In graph theory, a random geometric graph is a random undirected graph drawn on a bounded region, eg. the unit torus [0, 1)2.It is generated by # Placing vertices at random uniformly and independently on the region # Connecting two vertices, u ,… … Wikipedia