# Chapter 43. Geometric Graphs

# Chapter 43. Geometric Graphs

A geometric graph is a graph drawn in the plane with vertices represented by points and edges represented by straight-line segments. Unlike a plane graph, a geometric graph may have crossing edges. The geometry of the drawing is part of the object being studied. Two drawings of the same abstract graph may therefore define different geometric graphs.

Geometric graphs connect graph theory with discrete geometry, computational geometry, graph drawing, and spatial networks. They ask not only which vertices are adjacent, but also where the vertices are placed and how the edges sit in space. A standard definition treats a geometric graph as a straight-line drawing of a finite graph in the Euclidean plane.

## 43.1 Abstract Graphs and Geometric Graphs

An abstract graph records vertices and edges. It does not record positions, lengths, angles, or crossings.

A geometric graph adds a geometric realization. Each vertex is assigned to a distinct point in the plane. Each edge is drawn as the straight-line segment joining its two endpoints.

Thus the abstract graph

$$
G = (V,E)
$$

becomes geometric only after a placement map

$$
p : V \to \mathbb{R}^2
$$

has been chosen.

If \(uv \in E\), then the edge \(uv\) is drawn as the segment from \(p(u)\) to \(p(v)\).

The same abstract graph may have many geometric realizations. These realizations may differ in edge lengths, crossings, convexity, symmetry, and visibility properties.

## 43.2 Straight-Line Edges

The defining feature of a geometric graph is that its edges are straight. This differs from a topological graph, where edges may be arbitrary continuous curves connecting their endpoints. In common usage, geometric graphs use straight-line edges, while topological graphs allow curved edges.

| Object | Vertex representation | Edge representation |
|---|---|---|
| Abstract graph | Unspecified | Unspecified adjacency |
| Topological graph | Points | Curves |
| Geometric graph | Points | Straight-line segments |
| Plane straight-line graph | Points | Noncrossing straight-line segments |

A geometric graph may have crossings. A plane straight-line graph is a geometric graph with no edge crossings except at common endpoints.

## 43.3 General Position

Many results in geometric graph theory assume that the vertex set is in general position. The most common condition is that no three vertices are collinear.

This assumption prevents degenerate cases. If three vertices lie on one line, then an edge between two of them may pass through the third vertex. Such cases complicate definitions of crossing, visibility, triangulation, and face structure.

Under the no-three-collinear assumption, two edges either share an endpoint, cross at a single interior point, or do not meet.

General position is not always required, but it gives a clean setting for the basic theory.

## 43.4 Crossings

Two edges cross if their straight-line segments intersect at an interior point of both edges.

Edges that share an endpoint are adjacent, but they are not said to cross at that endpoint. Crossings are unintended intersections between edges that do not share a vertex.

For example, suppose the vertices of a quadrilateral are arranged in convex position:

$$
a,b,c,d.
$$

The edges \(ac\) and \(bd\) are diagonals. They cross in the interior of the quadrilateral.

Crossings distinguish geometric graphs from plane graphs. A graph may be planar as an abstract graph, yet a particular geometric drawing of it may contain crossings.

## 43.5 Plane Straight-Line Graphs

A plane straight-line graph is a geometric graph with no crossings. Its edges form a planar embedding using line segments.

Every simple planar graph can be drawn as a plane straight-line graph. This result is known as Fary's theorem. It shows that curved edges are not needed to draw simple planar graphs without crossings.

Thus, for simple planar graphs, the following two statements are equivalent:

| Statement | Meaning |
|---|---|
| The graph is planar | It has a crossing-free drawing with curves |
| The graph has a plane straight-line drawing | It has a crossing-free drawing with segments |

This equivalence is important in graph drawing. It permits planar graphs to be studied using geometry without changing the class of graphs.

## 43.6 Complete Geometric Graphs

A complete geometric graph is obtained by placing \(n\) points in the plane and joining every pair by a straight-line segment. Its underlying abstract graph is \(K_n\).

If the points are in convex position, then the drawing is especially structured. The vertices lie on the boundary of a convex polygon, and the edges are its sides and diagonals.

Complete geometric graphs are central in extremal geometric graph theory. They provide a natural setting for studying crossings, noncrossing subgraphs, triangulations, matchings, and Ramsey-type problems.

For \(n \geq 5\), the complete graph \(K_n\) is nonplanar as an abstract graph. But even for smaller values of \(n\), different geometric placements may produce different crossing patterns.

## 43.7 Euclidean Lengths

Once vertices are points in the plane, each edge has a Euclidean length. If an edge joins vertices \(u\) and \(v\), its length is

$$
\|p(u)-p(v)\|.
$$

This metric information is absent from an abstract graph.

A geometric graph may therefore be studied as a weighted graph where edge weights are induced by distance. This viewpoint leads to Euclidean minimum spanning trees, geometric shortest paths, spanners, proximity graphs, and network design problems.

In a Euclidean complete graph, every pair of points is joined by an edge whose weight is their Euclidean distance.

## 43.8 Proximity Graphs

A proximity graph is a geometric graph whose edges are determined by distance or neighborhood rules.

Common examples include:

| Graph | Edge rule |
|---|---|
| Unit disk graph | Join points at distance at most a fixed radius |
| Nearest-neighbor graph | Join each point to one or more nearest points |
| Gabriel graph | Join two points if a certain disk contains no other point |
| Relative neighborhood graph | Join points if no third point is closer to both |
| Delaunay graph | Join points whose Voronoi cells share a boundary |

These graphs model local interaction. They appear in wireless networks, clustering, mesh generation, and computational geometry.

The key difference from an arbitrary graph is that adjacency is constrained by geometry.

## 43.9 Triangulations

A triangulation of a point set is a maximal plane straight-line graph on that point set. Maximal means that no additional straight-line edge can be added without creating a crossing.

If the points are in general position and the graph is maximal planar on the point set, then every bounded face is a triangle. The outer face is bounded by the convex hull of the point set.

Triangulations are among the most important geometric graphs. They decompose a point set into triangular regions. They are used in interpolation, mesh generation, finite element methods, graphics, and computational geometry.

A Delaunay triangulation is a special triangulation defined by an empty-circle condition. It is dual to the Voronoi diagram of the same point set in the nondegenerate case. Geometric graph theory treats such structures as graphs with strong metric constraints.

## 43.10 Convex Position

A finite point set is in convex position if every point lies on the boundary of its convex hull.

Graphs drawn on point sets in convex position are easier to analyze because the vertices occur in a circular order. Edges are chords of a convex polygon. Two edges cross exactly when their endpoints alternate around the boundary.

For vertices

$$
a,b,c,d
$$

in clockwise order, the edges \(ac\) and \(bd\) cross.

Convex position is a common setting for geometric extremal problems. It removes many complications caused by points inside the convex hull.

## 43.11 Geometric Isomorphism

Two geometric graphs may have the same underlying abstract graph but different geometry. They may differ in the order of vertices, edge crossings, lengths, or orientations.

An abstract graph isomorphism preserves adjacency. A geometric isomorphism may require more, depending on the context. It may preserve crossings, order type, distances, or orientation.

For example, two drawings of \(K_4\) can have different crossing behavior. If all four vertices are in convex position, the two diagonals cross. If one vertex lies inside the triangle formed by the other three, the drawing has no crossing. The abstract graph is the same, but the geometric graphs differ.

## 43.12 Geometric Graphs and Planarity

Planarity is a property of an abstract graph. A geometric graph is already drawn.

These two ideas must be separated:

| Question | Type |
|---|---|
| Can this abstract graph be drawn without crossings? | Planarity |
| Does this particular straight-line drawing have crossings? | Geometric drawing property |
| Can this point placement support a crossing-free drawing of the graph? | Geometric embeddability |

A planar graph may be drawn with crossings if the drawing is careless. Fary's theorem says that some straight-line crossing-free drawing exists, but it may require changing vertex positions.

If the vertex positions are fixed, a crossing-free drawing may no longer be possible for a given edge set.

## 43.13 Applications

Geometric graphs occur whenever adjacency depends on spatial location.

| Area | Use |
|---|---|
| Wireless networks | Vertices are devices, edges represent communication range |
| Robotics | Edges represent feasible motion or visibility |
| Computational geometry | Triangulations, Voronoi-Delaunay structures, proximity graphs |
| Graphics | Meshes and surface approximations |
| Geographic information systems | Road, river, and spatial adjacency networks |
| Scientific computing | Finite element meshes |
| Data analysis | Neighborhood graphs for clustering and manifold learning |

The graph supplies combinatorial structure. The embedding supplies metric and spatial structure.

## 43.14 Summary

A geometric graph is a graph drawn with vertices as points and edges as straight-line segments. It differs from an abstract graph because the placement of vertices and the geometry of edges matter. It differs from a plane graph because crossings may be allowed.

The main ideas are:

| Concept | Meaning |
|---|---|
| Geometric graph | Straight-line drawing of a graph |
| Plane straight-line graph | Crossing-free geometric graph |
| Topological graph | Drawing with curved edges |
| General position | Usually no three vertices collinear |
| Crossing | Interior intersection of two nonadjacent edges |
| Proximity graph | Edges defined by metric rules |
| Triangulation | Maximal crossing-free straight-line graph on a point set |

Geometric graphs provide a bridge from graph theory to geometry. They retain the discrete structure of vertices and edges, while adding position, length, crossing, convexity, and metric constraints.