Walking face by face

 

To understand a BFS "walking face by face," we first need to clarify some fundamental concepts:

1. Planar Graphs are Essential: The concept of "faces" (regions bounded by edges) only applies to planar graphs – graphs that can be drawn on a plane without any edges crossing. An "arbitrary graph" might not be planar, so the idea of "walking face by face" wouldn't be well-defined without this prerequisite. For this discussion, we'll assume the arbitrary graph chosen is indeed planar.

2. The Dual Graph is the Key: When we talk about "walking face by face," we are conceptually performing a standard Breadth-First Search (BFS) on the graph's dual graph.

   • The vertices of the dual graph correspond to the faces of the original planar graph.

   • An edge exists between two vertices in the dual graph if their corresponding faces in the original graph share a common boundary edge.

Conceptualizing "BFS Walking Face by Face"

Given a planar graph G:

1. Construct G* (the Dual Graph):

   • Identify all the faces of your planar graph G (including the outer unbounded face). Each face Fi becomes a vertex vi* in your dual graph G*.

   • For every edge e in G, if e is shared by two faces Fj and Fk, draw an edge between vj* and vk* in G*. (If e is a bridge, meaning it bounds the same face twice, it corresponds to a loop in G*).

2. Choose a "Root Face":

   • Select an arbitrary starting face in your original graph G. This face will be your "root" for the BFS, effectively becoming the starting vertex in G*.

3. Perform Standard BFS on G*:

   • Apply the regular Breadth-First Search algorithm, but operate on the vertices and edges of the dual graph G*.

   • BFS will explore adjacent faces (which are connected by sharing an edge in the original graph) level by level.

"Distance" and "Optimal Path" in this Context

• Distance: The "distance from the root face" (unweighted) would be the minimum number of "face transitions" (i.e., the number of edges in G*) required to get from the starting "root face" to any other face.

• Optimal Path: Yes, by definition, BFS will find an optimal path in this context. Just as a standard BFS finds the shortest path in terms of the number of edges between vertices in an unweighted graph, a BFS performed on the dual graph (G*) will find the shortest path in terms of the minimum number of shared boundary edges (face transitions) between the "root face" and any other reachable face.

"If the vertex are connect in a sequential way..."

This part of your question introduces a specific structural characteristic.

• If you mean the vertices of the original graph G are connected sequentially (e.g., G is a simple path or cycle graph), then its dual graph G* will also have a very specific, often simple, structure. For instance, the dual of a simple cycle (like a square) is two vertices connected by parallel edges (a multigraph). A BFS on such a G* would still find an optimal path.

• If you mean the vertices of the dual graph G* itself are connected sequentially (i.e., G* is a path graph or a cycle graph), then the BFS will simply traverse that existing sequential path, and the "optimal path" would trivially be that sequence of faces.

In essence, the core idea of "BFS walking face by face" is precisely what happens when you run a standard BFS algorithm on the dual graph of a planar graph. The "optimal path" is then the shortest sequence of face transitions.