🔢 mathematics

Breadth-First Search in Succinct Planar Graphs

This paper presents a succinct encoding for planar graphs that enables direct breadth-first search execution and supports various fundamental graph operations, such as computing balanced separators and tree decompositions, within optimal $O(n)$ time and $o(n)$ additional space.

Original authors: Johannes Meintrup

Published 2026-07-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes Meintrup

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, intricate map of a city (a graph) drawn on a piece of paper. Usually, to navigate this city, you need a huge notebook to write down every street, every intersection, and every turn you make. If the city has a million intersections, your notebook becomes impossibly large, taking up too much memory on your computer.

This paper introduces a clever way to shrink that map down to its absolute smallest possible size—like folding a giant map into a tiny pocket square—without losing any of the ability to navigate it. Even better, it shows how to perform a specific type of navigation called Breadth-First Search (BFS) directly on this tiny, folded map, and then keep a "tree" of your journey available for quick questions, all while using almost no extra memory.

Here is a breakdown of the paper's ideas using everyday analogies:

1. The Problem: The "Heavy" Map

In computer science, a graph is just a collection of points (vertices) connected by lines (edges). A planar graph is one that can be drawn on a flat surface without any lines crossing (like a subway map or a circuit board).

Normally, to run a BFS (which explores a graph layer by layer, like ripples spreading out from a stone dropped in a pond), you need to store a lot of extra data:

A queue of places to visit.
A list of who you've already visited.
A record of your path (the "BFS tree").

For a large graph, this extra data takes up a lot of space. The paper wants to do this using almost no extra space (specifically, "sublinear" space, meaning less than the size of the graph itself).

2. The Solution: The "Nested Division" (The Russian Doll Strategy)

The authors use a technique called a Succinct Nested Division. Think of this like a set of Russian nesting dolls, but for a city map:

The Big Doll (Mini Pieces): First, they chop the giant city into medium-sized neighborhoods.
The Small Dolls (Micro Pieces): Then, they chop those neighborhoods into tiny blocks.
The Lookup Table: The tiny blocks are so small that instead of drawing them out every time, the computer just looks them up in a pre-made "dictionary" or "menu." If a block looks like "Type A," the computer just says, "Ah, I know Type A," and pulls up the info instantly.

This allows the computer to store the entire map using the absolute minimum number of bits required by math (the "information-theoretic minimum").

3. The Magic Trick: Running BFS on the Folded Map

The main achievement of the paper is running the BFS directly on this compressed map without unfolding it first.

How it works: Imagine you are exploring the city. Instead of walking every single street, you jump from neighborhood to neighborhood.
The "Table-Swap": When you enter a tiny block (a micro piece), the computer doesn't re-calculate the whole block. It performs a "table-swap." It's like flipping a card in a deck. The card says, "If you enter this block from the North, here is exactly where you exit and what you see."
The Result: The computer figures out the shortest path to every building in the city in linear time (fast), using almost no extra memory.

4. The "Tree" That Stays Available

Usually, when you finish a search, you throw away the path you took. But this paper keeps the BFS Tree (the map of your journey) available inside the tiny folded map.

Once the search is done, you can ask the map questions instantly, like:

"Who is the parent of this building?" (Who did we come from?)
"What floor is this building on?" (How far is it from the start?)
"Who is the closest common ancestor of these two buildings?" (Where did our paths merge?)

The paper claims you can answer these questions in constant time (instantly), even though the map is compressed.

5. The "Interdigitating Tree" (The Dual Map)

For maps drawn on a flat surface (plane graphs), there is a cool side effect. If you draw a tree through the city streets, there is a corresponding "dual tree" that weaves through the spaces between the streets (the blocks).

The paper shows you can traverse this "dual tree" easily. Imagine walking through the city blocks instead of the streets. This allows for advanced tricks, like finding a Separator.

6. The "Separator" (Cutting the Cake)

One of the most famous problems in graph theory is the Planar Separator Theorem. It says you can always cut a planar map into two roughly equal halves by removing a small number of key intersections (about the square root of the total size).

The Paper's Application: Using their tiny map and the BFS tree, the authors show how to find this "cut" very quickly.
The Metaphor: Imagine you have a giant, round cake (the graph). You want to cut it into two equal halves with a single knife stroke, but you can only cut through a few specific points. The paper provides a method to find those few points instantly, using almost no memory. This is useful for breaking down huge problems into smaller, manageable chunks.

7. Other Cool Tricks

Checking for "Bipartiteness": This is a fancy way of asking, "Can we color this map with only two colors (like a checkerboard) so no two touching spots have the same color?" The paper shows you can check this instantly by looking at the "layers" of your BFS tree.
Triangulation: They show how to turn any map into a map where every area is a triangle (like a mesh), which makes calculations easier, all while keeping the map compressed.

Summary of Claims

The paper does not claim to solve medical problems or predict the future. It strictly claims:

Space Efficiency: You can store a planar graph in the smallest possible space.
Speed: You can run a Breadth-First Search on this tiny storage in linear time (fast).
Accessibility: You can keep the resulting path (tree) and ask questions about it (parent, child, depth) instantly.
Applications: You can use this to find "separators" (cuts) in the graph, check if a graph is bipartite, or build a tree decomposition, all while using almost no extra memory.

In short, the authors have built a super-efficient, pocket-sized navigation system for flat maps that lets you explore, remember your path, and solve complex cutting puzzles without ever needing a big notebook.

Problem Statement

The paper addresses the challenge of performing space-efficient graph traversal algorithms, specifically Breadth-First Search (BFS), on planar graphs while maintaining the resulting BFS tree as an accessible data structure. Standard BFS algorithms in the word-RAM model require $\Theta(n \log n)$ bits to store visitation status and a queue, which is prohibitive for space-constrained environments. While previous works have achieved space-efficient BFS and Depth-First Search (DFS) using $O(n)$ bits, they typically output vertices in visitation order without retaining the traversal tree for subsequent queries (e.g., parent/child queries, layer queries, or Lowest Common Ancestor). This lack of structural access limits the utility of such traversals as subroutines in more complex algorithms. The specific goal is to construct a succinct encoding of planar graphs that supports direct BFS execution using $o(n)$ additional bits, while keeping the computed BFS tree available for standard tree operations in constant time per query.

Methodology

The proposed solution builds upon the succinct nested division framework introduced by Blelloch and Farzan and extended by Elberfeld et al. for DFS. The methodology involves several key components:

Succinct Nested Division: The input planar graph is decomposed into a hierarchy of "mini pieces" and "micro pieces" using an $r$ -division strategy.
- Mini pieces are of size $r_0 = \text{poly}(\log n)$ and contain $O(r_0^{1/2+\epsilon})$ boundary vertices.
- Micro pieces are smaller, of size $r_1 = \text{poly}(\log \log n)$ , and are small enough to be represented by indices into a precomputed lookup table.
- The encoding stores the connectivity between pieces and uses compressed indexable dictionaries to map global vertex labels to local labels within pieces.
Triangulation: To facilitate the BFS, the paper first presents a procedure to triangulate biconnected plane graphs within the succinct encoding. This involves adding auxiliary edges between boundary vertices to ensure that faces are either entirely within a micro piece or consist solely of boundary vertices. This step is performed in expected $O(n)$ time for the succinct variant and deterministic $O(n)$ time for a compact variant.
BFS Execution via Table-Swap: The core algorithm executes BFS directly on the encoding without explicitly storing the full queue or visitation array.
- State Representation: The BFS state is maintained by tracking "active" mini and micro pieces. For micro pieces, the state is encoded as a "partial BFS state" consisting of a boundary profile (colors indicating visited/unvisited status and current layer processing) and a local advance counter.
- Table-Swap Operations: The lookup table for micro pieces supports a "table-swap" operation. Given the current boundary profile and local advance, the table returns the next state, newly reached boundary vertices, and whether the piece remains active. This allows the BFS to progress through micro pieces in $O(1)$ time per operation.
- Synchronization: When a boundary vertex is reached, its layer and parent information are propagated to all other pieces containing that vertex (boundary synchronization). This is handled explicitly for exceptional cases and via table operations for standard cases.
Tree Maintenance: The resulting BFS tree is implicitly stored within the encoding. The parent pointers and layer information for boundary vertices are stored explicitly, while internal vertices are handled via the lookup table states.

Key Contributions and Results

The paper presents the following main results:

Succinct BFS Encoding: A succinct encoding for connected planar graphs that allows computing a BFS tree rooted at any vertex $s$ in $O(n)$ time using $o(n)$ additional bits.
Query Support: Once computed, the BFS tree supports constant-time queries for:
- Traversal (preorder, postorder, BFS order).
- Layer queries ( $\ell(u)$ ).
- Parent and child iteration.
- Tree edge vs. non-tree edge testing.
- Lowest Common Ancestor (LCA) queries.
Construction Complexity:
- Succinct Variant: Constructed in expected $O(n)$ time using $O(n)$ bits during construction.
- Compact Variant: Constructed in deterministic $O(n)$ time using $O(n)$ bits.
Applications:
- Planar Separator Theorem: The encoding enables the computation of a balanced separator of size $O(\sqrt{n})$ for biconnected plane graphs in $O(n)$ time using $o(n)$ additional bits. This is achieved by finding a balanced shortest-path cycle separator using the interdigitating tree (the dual spanning tree of non-tree edges).
- Bipartiteness Testing: A sublinear-space test for bipartiteness is provided, running in $o(n)$ time by checking the parity of BFS layers for non-tree edges.
- Tree Decomposition: An implicit tree decomposition of width $O(d)$ (where $d$ is the graph diameter) is derived from the BFS tree and the interdigitating tree, with bags traversable in linear time.
- Generalization: The results regarding BFS computation and tree queries generalize to any separable graph class, provided a succinct nested division is available, though the specific construction time and space guarantees for planar graphs may not hold for all separable classes.

Significance

The paper claims to fill a critical gap in space-efficient graph algorithms. While previous work (Elberfeld et al.) successfully adapted succinct encodings for DFS, the authors note that BFS presents unique challenges because it is not as "local" as DFS; a BFS tree must preserve shortest-path distances, meaning a search cannot simply exhaust a subgraph locally without considering potential shorter paths entering through other boundary vertices.

The significance of this work lies in demonstrating that despite these challenges, a BFS tree can be computed and maintained within the succinct encoding using only $o(n)$ additional bits. This capability enables the implementation of complex graph algorithms, such as the planar separator theorem, in sublinear space while retaining the structural access to the traversal tree that is often required for correctness and efficiency. The ability to perform these operations on unlabeled graphs (preserving isomorphism) makes the encoding suitable for decision problems and specific solution tracking, even if arbitrary vertex labels are not preserved. The work extends the applicability of succinct data structures from simple traversal outputs to full structural representations of traversal trees.