\n
## Algorithm Pseudocode: 2p-prop
### Overview
The image displays a pseudocode algorithm titled "Algorithm 2: 2p-prop". It is a technical procedure for partitioning a set of arcs (edges) into two distinct sets or "planes," denoted as \(P_1\) and \(P_2\). The algorithm appears designed to handle geometric or graph-based constraints, specifically managing arcs that cross each other by assigning them to different planes to avoid conflicts.
### Components/Axes
The algorithm is structured with the following components:
* **Title:** Algorithm 2: 2p-prop
* **Input:** A set of arcs \(T\), and input length \(n\).
* **Result:** Two sets (planes) of arcs \(P_1, P_2\).
* **Function Definition:** A helper function named `Propagate`.
* **Main Algorithm Body:** Initialization and nested loops that process potential arcs.
* **Control Flow Elements:** `for` loops, `if-else` conditionals, and recursive function calls.
* **Mathematical/Set Notation:** Uses symbols for assignment (\(\leftarrow\)), set union (\(\cup\)), empty set (\(\emptyset\)), element membership (\(\in, \notin\)), existential quantifier (\(\exists\)), logical OR (\(\lor\)), and set complement (overline, e.g., \(\overline{P_1}\)).
### Detailed Analysis
The pseudocode is transcribed verbatim below.
**Function Propagate:**
```
function Propagate(Edge sets T, \overline{P_1}, \overline{P_2}, Edge e, Plane i):
\overline{P_i} ← \overline{P_i} ∪ {e};
// e forbidden from plane i
for (e' ∈ T | e' crosses e) do
if e' ∉ \overline{P_{3-i}} then
(\overline{P_1}, \overline{P_2}) ← Propagate(T, \overline{P_1}, \overline{P_2}, e', 3 - i);
end
end
return \overline{P_1}, \overline{P_2};
```
**Main Algorithm:**
```
P_1 ← ∅, P_2 ← ∅, \overline{P_1} ← ∅, \overline{P_2} ← ∅;
for x_r ← 1 to n do
for x_l ← x_r - 1 downto 0 do
if ∃ a ∈ T | a = (x_l, x_r, l) ∨ a = (x_r, x_l, l) then
nextArc ← a;
if nextArc ∉ \overline{P_1} then
P_1 ← P_1 ∪ {nextArc};
Propagate(T, \overline{P_1}, \overline{P_2}, nextArc, 2);
else if nextArc ∉ \overline{P_2} then
P_2 ← P_2 ∪ {nextArc};
Propagate(T, \overline{P_1}, \overline{P_2}, nextArc, 1);
else
do nothing (failed to assign nextArc to a plane);
end
end
end
end
return P_1, P_2;
```
### Key Observations
1. **Constraint Propagation:** The core logic is in the `Propagate` function. When an arc `e` is assigned to a plane `i`, it is added to the *forbidden set* for that plane (\(\overline{P_i}\)). The function then recursively processes all other arcs `e'` in the input set `T` that cross `e`. If such a crossing arc `e'` is not already forbidden from the *opposite* plane (`3-i`), it is recursively propagated, effectively forbidding it from the plane where `e` resides and attempting to assign it to the other plane.
2. **Greedy Assignment with Backtracking:** The main algorithm iterates through potential arc coordinates \((x_l, x_r)\). For each existing arc `a` found in `T`, it attempts a greedy assignment: first to plane \(P_1\), then to plane \(P_2\), if the arc is not forbidden from that plane. The `Propagate` call enforces the crossing constraint globally.
3. **Failure State:** An arc can only fail to be assigned if it is already forbidden from *both* planes (\(\overline{P_1}\) and \(\overline{P_2}\)), at which point the algorithm does nothing for that arc.
4. **Spatial Layout:** The pseudocode is presented in a standard, indented format. The `Propagate` function is defined at the top, followed by the main algorithm body. The nested loop structure (`for x_r`, `for x_l`) is clearly indented, as are the conditional blocks.
### Interpretation
This algorithm, "2p-prop" (likely short for "2-plane propagation"), is a method for **graph drawing or geometric embedding**. Its purpose is to take a set of arcs (which could represent edges in a graph drawn with vertices on a line, where an arc \((x_l, x_r)\) connects positions \(x_l\) and \(x_r\)) and partition them into two layers or planes. The key constraint is that **arcs which cross each other cannot be in the same plane**.
The `Propagate` function implements a constraint satisfaction mechanism. Assigning an arc to a plane creates a "forbidden zone" for all arcs that cross it. This is a classic approach to achieving a **planar embedding** or a **2-layer drawing** of a graph, which is crucial in areas like VLSI circuit design, network visualization, and phylogenetic tree layout. The algorithm's success depends on the structure of the input set `T`; if the graph is not 2-planar (cannot be drawn without crossings using only two layers), some arcs will remain unassigned. The nested loops suggest it processes arcs in a specific order, likely based on their right endpoint (\(x_r\)), which is a common strategy in dynamic programming solutions for such problems.
