1 Overview of Face Adjacency Graphs

1.1 Definition via regions (faces)

A face adjacency graph is a graph whose nodes correspond to the faces (regions) of a planar subdivision. For a planar map or polygonal partition, the subdivision breaks a plane area into connected regions separated by edges. Each such region becomes a vertex in the adjacency graph, allowing the subdivision’s “region-to-region” structure to be studied using graph theory.

1.2 Definition via adjacency criteria (shared edge vs shared vertex)

Two faces are typically considered adjacent when their closures share a boundary segment of positive length. Under this common convention, adjacency reflects direct boundary contact along an edge of the planar drawing. Some variants instead declare faces adjacent if they meet at a point (shared vertex), even when they do not share an edge segment. The choice of criterion affects degree distributions and cycle structure in the resulting graph.

1.3 Relationship to dual graphs

Face adjacency graphs are closely related to graph duality. Given a planar embedding of a graph, the dual graph often uses faces of the embedding as vertices and adjacency via shared primal edges. In many settings, the face adjacency graph is effectively the dual graph (possibly with the outer face handled in a particular way). Differences arise when the planar subdivision is not presented as an embedding of a single graph, or when adjacency is defined by vertex-touching rather than edge-sharing.

1.4 Variants and common conventions

Common conventions include:

  • Whether the unbounded outer region is included as a vertex.
  • Whether adjacency is defined by shared edge segments only, or also by shared points.
  • How the subdivision’s boundary components are treated when faces are separated by curves that meet at endpoints.

These choices influence the exact combinatorial object under study, though many qualitative properties remain stable across reasonable conventions.

2 Construction from a Planar Embedding

2.1 Input model: planar map, polygon mesh, or arrangement

Construction begins with a representation of a planar subdivision. Inputs include planar maps (a combinatorial embedding of edges), polygon meshes (piecewise-linear surfaces in a planar setting), or arrangements of curves that partition the plane. In computational geometry, the input may be given explicitly as polygonal boundaries, as a mesh connectivity structure, or as a collection of edges embedded in the plane.

2.2 Identifying faces and boundary cycles

The faces of the subdivision are found by tracing boundary cycles. In a combinatorial embedding, each directed edge belongs to a face on its left (or right), allowing traversal of face boundaries by following successor links. In a polygonal representation, faces can be obtained by planar subdivision methods that build a topological structure capturing how edges connect and where the interior of each region lies.

Each face is then associated with one or more boundary cycles. Simple connected regions often yield a single cycle; regions with holes may require multiple cycles that collectively describe the region’s boundary structure.

2.3 Determining adjacency between faces

Once faces are identified, adjacency is determined by examining shared boundary elements. Under the edge-sharing convention, each boundary segment that separates two faces induces an adjacency between the corresponding vertices in the adjacency graph. If vertex-sharing adjacency is allowed, endpoints where multiple faces meet create edges between their corresponding nodes, even when no separating segment has positive length.

For subdivisions produced from embeddings, the adjacency determination can be implemented systematically by iterating over primal edges and checking which face lies on each side.

2.4 Building vertices and edges in the adjacency graph

To build the face adjacency graph:

  1. Create a vertex for each face in the planar subdivision (including, optionally, the outer face).
  2. For each separating boundary segment according to the chosen criterion, add an edge between the two incident faces’ vertices.
  3. If multiple boundary segments separate the same pair of faces, the result may be a simple graph (single edge per pair) or a multigraph (multiple edges). Many works use a simple graph to focus on combinatorial reachability, while multigraph variants can capture local multiplicity.

2.5 Handling degenerate cases (holes, touching boundaries)

Degenerate situations can occur in practical inputs:

  • Holes: A face with interior voids may have several boundary cycles; adjacency should consider segments that actually separate distinct regions.
  • Touching boundaries: If two regions meet only at a point, edge-sharing rules treat them as non-adjacent, while vertex-sharing rules treat them as adjacent.
  • Nearly coincident edges or duplicated segments: Robust face identification must avoid creating spurious tiny faces or missing boundaries. Conceptually, the goal is to interpret the subdivision as a well-defined planar partition before building adjacency.

3 Graph-Theoretic Properties

3.1 Connectivity and component structure

The face adjacency graph reflects how regions connect through shared boundaries. If the planar subdivision covers a connected domain and faces are separated only by internal boundaries, the adjacency graph is often connected when the outer face is included. Excluding the outer face can yield multiple components if some regions are enclosed by others without sharing boundaries under the chosen adjacency rule.

Component structure depends on whether “touching” is counted as adjacency and on how the subdivision domain is bounded.

3.2 Degrees and local neighborhood sizes

The degree of a face-vertex equals the number of distinct neighboring faces that satisfy the adjacency criterion. Faces with long, intricate boundary curves may touch many other regions, producing higher degrees. Under edge-sharing adjacency, a region can have degree bounded by the number of separating boundary segments; under vertex-sharing adjacency, degrees may increase due to point contacts that join many regions at a single meeting point.

Local neighborhood size thus encodes how crowded the region’s boundary environment is.

3.3 Planarity and embeddability considerations

Although a face adjacency graph is derived from a planar subdivision, it is not always itself planar in a straightforward geometric sense. In many standard cases—especially when it corresponds to the dual of a planar embedding—the dual graph is planar as a graph-theoretic dual object (duality preserves planarity up to standard transformations). However, if the subdivision includes complicated identifications or if adjacency is defined by vertex-touching, the resulting graph may not correspond to a simple planar dual and can realize structures that challenge planarity.

In practice, the most reliable statements come from relating the adjacency graph to a known dual construction under a consistent embedding model.

3.4 Cycles, bipartiteness, and parity observations

Cycles in the face adjacency graph correspond to sequences of regions where consecutive regions share boundaries. In planar settings derived from consistent edge-sharing adjacency, parity properties can sometimes be related to coloring arguments on the underlying subdivision. For example, if the dual graph is bipartite, it corresponds to a two-coloring of faces such that adjacent faces receive opposite colors, which implies constraints on the subdivision’s structure.

Such properties often depend on whether the primal embedding supports a corresponding vertex-coloring or face-coloring without contradictions.

3.5 Relationship between face adjacency counts and Euler characteristics (discrete form)

Euler’s formula relates the number of vertices, edges, and faces of a planar embedding. When the face adjacency graph is interpreted as a dual-like structure, counts of adjacency edges relate to counts of primal edges that separate faces. In the edge-sharing model, each primal edge corresponds to an adjacency between the two faces incident to that edge (or to a loop in special cases). Summing these correspondences yields discrete relationships between:

  • the number of adjacency graph vertices (faces of the subdivision),
  • the number of adjacency graph edges (separating boundary segments),
  • and other combinatorial quantities determined by the primal embedding.

In particular, global constraints from Euler characteristics limit what degree sequences and cycle counts can occur simultaneously.

4 Face Adjacency in Polygonal Meshes

4.1 Triangulated vs general polygonal meshes

Polygonal meshes can be triangulated or consist of polygons of varying sizes. In triangulated meshes, adjacency relationships between surface elements are simpler to trace because each internal mesh edge separates exactly two triangles (in typical manifold-like meshes). This tends to make face adjacency graphs closer to uniform local structure. General polygonal meshes may create faces with boundaries that involve multiple vertices and edges, which can change degree patterns and how adjacency must be computed.

4.2 Edge-based adjacency on meshes

For a mesh embedded in a plane (or for a planar domain triangulation), edge-based adjacency often matches the standard edge-sharing criterion. Each mesh edge either lies on the boundary between a mesh face and the exterior region or between two mesh faces. When the adjacency graph is built from these mesh faces, the result captures how triangles or polygons sit next to each other along shared edges.

4.3 Influence of mesh refinement on adjacency structure

Refinement subdivides elements, increasing the number of faces and edges in the underlying mesh. As a result, the adjacency graph typically gains more vertices and edges, and local degrees can change because boundaries become more segmented. However, certain coarse structural features—such as overall connectivity and the existence of separating cycles—may persist across refinements. This motivates considering adjacency graphs at different resolution levels in computational workflows.

4.4 Scattered/isolated faces and how they appear as graph components

Not all meshes represent a connected planar region. Disconnected components in the geometric domain lead to disconnected components in the adjacency graph, because faces do not share boundaries across gaps. Isolated faces that only touch the rest of the mesh through point contacts may appear differently depending on adjacency criterion: with edge-sharing, such a face becomes an isolated vertex component; with vertex-sharing, it may connect to others through adjacency edges induced by shared endpoints.

5 Algorithmic Aspects

5.1 Face enumeration methods (outline of approaches)

Computing faces is often the core difficulty. Typical approaches include:

  • Half-edge or directed-edge traversal: using successor relationships to walk along face boundaries.
  • Planar subdivision via arrangement processing: constructing vertices and edges, then assembling faces from local adjacency.
  • Topological embedding reconstruction: deriving a combinatorial embedding from geometric segments and then using embedding-based traversal.

These methods differ in implementation complexity and robustness requirements, especially when inputs are given numerically.

5.2 Efficient adjacency detection using edge records

After faces are enumerated, adjacency can be computed efficiently. A common strategy is to iterate over each primal edge and determine the two incident faces on its two sides. The adjacency graph then receives an edge between those corresponding face-vertices. With appropriate indexing (face IDs and edge-to-side relationships), this step becomes near-linear in the number of primal edges.

If multiedges are allowed, multiple boundary segments between the same pair of faces contribute multiple adjacency edges; if a simple graph is desired, duplicate insertions can be prevented using hashing or adjacency marking.

5.3 Complexity considerations

Let the planar subdivision have \(F\) faces, \(E\) edges, and \(V\) vertices. Face enumeration is often proportional to the size of the embedding (commonly \(O(E)\) for traversal-based methods once the embedding structure exists). Building adjacency by scanning edges is also typically \(O(E)\), plus overhead for deduplication if a simple graph representation is used. Overall, a well-structured pipeline tends to have linear or near-linear time in the input size.

Worst-case performance can worsen when geometric preprocessing dominates, such as when computing an exact planar subdivision from imprecise coordinates.

5.4 Data structures for representing faces and boundaries

Efficient implementation commonly uses:

  • Half-edge data structures: each directed edge references its twin (opposite direction), its origin vertex, and the next edge along the incident face boundary.
  • DCEL-like representations: a doubly connected edge list stores adjacency around vertices and faces in a consistent topology.
  • Face boundary lists: storing the cycle of boundary edge identifiers for each face.

These structures support both enumeration and subsequent adjacency construction by offering direct access to which face lies to the left/right of an edge.

5.5 Robustness with numerical precision issues (conceptual)

When coordinates are approximate, determining the topology of the planar subdivision can be error-prone. Conceptual robustness measures include:

  • snapping or clustering near-coincident vertices,
  • treating near-collinear overlaps carefully,
  • and defining consistent tolerances for deciding whether boundaries truly intersect.

Although these are geometry concerns, they impact face adjacency results because incorrect topology leads to wrong face splitting and erroneous adjacency edges. Many systems therefore separate “geometric exactness” (or tolerance-managed preprocessing) from “combinatorial graph construction.”

6 Applications in Discrete Mathematics and Computation

6.1 Region growing and labeling using adjacency

Face adjacency graphs provide a convenient abstraction for algorithms that propagate labels across a planar domain. Region growing can start from a seed face and iteratively visit neighbors, using graph search (BFS/DFS) on the adjacency graph. This enables tasks such as segment labeling, iterative refinement, and computing neighborhoods of bounded graph distance.

6.2 Connectivity queries between regions

If one wants to know whether two regions are connected through a chain of boundary-sharing steps, the adjacency graph turns that question into a standard reachability problem. Connectivity checks, shortest paths (by hop count), and existence of separating sets can be expressed using common graph algorithms applied to the adjacency graph.

6.3 Combinatorial analysis of planar subdivisions

Researchers analyze planar subdivisions by studying derived combinatorial invariants. The face adjacency graph encodes how regions interact, supporting investigations of degree distributions, cycle structure, and constraints related to planarity and Euler characteristic. Such analysis can help classify subdivisions or compare different partitionings of the same geometric domain.

6.4 Constructing derived graphs for further reasoning

From the face adjacency graph, additional structures can be built, such as:

  • spanning trees for hierarchical region decomposition,
  • quotient graphs after merging similar regions,
  • or line graphs and other derived transformations in which adjacency patterns become the main object.

These constructions support multi-stage reasoning pipelines in computational geometry and discrete mathematics.

6.5 Teaching/visualization: map-coloring style reasoning (graph coloring context)

Face adjacency graphs naturally model map-coloring problems, where each face is a “country” and adjacent countries must satisfy coloring constraints. Even in contexts meant for education or visualization, the graph abstraction clarifies how local adjacency rules translate into global coloring feasibility, illustrating fundamental ideas in graph coloring and constraint satisfaction.

7 Examples and Worked Computations

7.1 Small planar maps with labeled faces

Consider a simple planar map where faces are labeled \(A, B, C,\dots\). After identifying which boundaries separate each labeled pair, one can list adjacency edges \((A,B)\), \((A,C)\), etc., directly from the map’s structure. The resulting adjacency graph makes it easy to verify statements like “face \(A\) touches exactly three other regions” by computing \(\deg(A)\).

7.2 Simple meshes and their adjacency graphs

For a triangulated quadrilateral subdivided into two triangles by a diagonal, the mesh has three faces if the outer region is included and two internal triangular faces if only bounded faces are used. The adjacency graph includes an internal edge adjacency between the two internal triangles, and each triangle may also be adjacent to the outer face along its boundary edges. This small example demonstrates how including or excluding the outer region changes the adjacency graph’s vertex set.

7.3 Comparing different adjacency criteria (edge-sharing vs vertex-sharing)

Take two regions that meet only at a point (like two “corners” touching). Under edge-sharing adjacency, no edge exists between their corresponding vertices in the adjacency graph. Under vertex-sharing adjacency, a connection appears, potentially changing bipartiteness, cycle presence, and degrees of the involved faces. Worked comparisons on the same map highlight how the criterion governs the graph’s combinatorial interpretation.

7.4 Verifying properties on example constructions

Given an example adjacency graph, one can verify properties such as:

  • connectivity (whether all face-vertices lie in one component),
  • degree constraints (which faces have many neighbors),
  • and cycle structure (existence of region loops).

Cross-checking these properties against the geometric map serves as a correctness test for both face enumeration and adjacency construction.