## Algorithm Pseudocode: 2p-greedy
### Overview
The image displays a formal pseudocode algorithm titled "Algorithm 1: 2p-greedy". It describes a greedy procedure for partitioning a set of arcs into two distinct planes, `P1` and `P2`, based on a non-crossing condition. The algorithm iterates through potential arc endpoints and attempts to assign arcs to planes where they do not cross existing arcs in that plane.
### Components/Axes
* **Algorithm Title:** `Algorithm 1: 2p-greedy`
* **Input Specification:** `Input: A set of arcs T, and input length n`
* **Result Specification:** `Result: Two sets (planes) of arcs P1, P2`
* **Initialization:**
* `P1 ← ∅;` (Initialize plane 1 as an empty set)
* `P2 ← ∅;` (Initialize plane 2 as an empty set)
* **Control Structures:**
* Outer loop: `for xr ← 1 to n do`
* Inner loop: `for xl ← xr - 1 downto 0 do`
* **Conditional Logic & Operations:**
* Existence check: `if ∃a ∈ T | a = (xl, xr, l) ∨ a = (xr, xl, l) then`
* Assignment: `nextArc ← a;`
* Set construction: `C ← {b ∈ (P1 ∪ P2) | b crosses a};`
* Plane assignment conditions:
* `if C ∩ P1 = ∅ then P1 ← P1 ∪ {nextArc};`
* `else if C ∩ P2 = ∅ then P2 ← P2 ∪ {nextArc};`
* `else do nothing (failed to assign nextArc to a plane);`
* **Termination:** `return P1, P2;`
### Detailed Analysis
The algorithm processes arcs defined by pairs of endpoints `(xl, xr)` and a label `l`. The core logic is as follows:
1. **Iteration Strategy:** It uses a nested loop structure. The outer loop variable `xr` iterates from 1 to `n`. The inner loop variable `xl` iterates backwards from `xr-1` down to 0. This suggests a systematic examination of all possible intervals `[xl, xr]` where `xl < xr`.
2. **Arc Identification:** For each `(xl, xr)` pair, it checks if an arc `a` exists in the input set `T` that matches either `(xl, xr, l)` or `(xr, xl, l)`. The `∨` (logical OR) indicates the arc's direction (left-to-right or right-to-left) may not matter for this check.
3. **Conflict Detection:** If such an arc `a` is found, the algorithm computes a set `C`. `C` contains all arcs `b` that are already in either plane (`P1 ∪ P2`) and that cross the current arc `a`.
4. **Greedy Assignment:** The algorithm then attempts a greedy, first-fit assignment:
* **First Priority (P1):** If `C` has no intersection with `P1` (`C ∩ P1 = ∅`), meaning no arc in plane `P1` crosses `a`, then `a` is added to `P1`.
* **Second Priority (P2):** If assignment to `P1` fails (due to crossing conflicts), it checks if `C` has no intersection with `P2` (`C ∩ P2 = ∅`). If true, `a` is added to `P2`.
* **Failure:** If both planes contain arcs that cross `a`, the algorithm does nothing for that arc, and it remains unassigned.
5. **Output:** After all iterations, the algorithm returns the two populated planes, `P1` and `P2`.
### Key Observations
* **Greedy & Online Nature:** The algorithm makes irrevocable decisions. Once an arc is assigned to a plane, it cannot be moved. The order of processing (determined by the loop order `xr` from 1 to `n`, and `xl` descending) critically influences the final partition.
* **Non-Crossing Constraint:** The fundamental rule is that arcs within the same plane must not cross each other. The set `C` explicitly models this constraint.
* **Potential for Unassigned Arcs:** The `else do nothing` clause indicates that not every arc in `T` is guaranteed to be placed. The algorithm may fail to find a valid plane for some arcs.
* **Symmetry in Input:** The check `a = (xl, xr, l) ∨ a = (xr, xl, l)` treats an arc and its reverse as equivalent for the purpose of identification and conflict checking.
### Interpretation
This pseudocode defines a heuristic algorithm for solving a **graph drawing** or **arc routing** problem, specifically a **2-page book embedding** or **2-stack layout** problem. The goal is to draw a set of arcs (edges) above a line (the "spine") using only two distinct layers (planes/pages) such that no two arcs on the same page cross.
* **What it does:** It attempts to pack arcs into two non-crossing layers. This is a classic problem in computational geometry and VLSI design, relevant for minimizing crossings in visualizations or optimizing wire routing in circuit layouts.
* **How elements relate:** The nested loops define the search space for potential arcs. The conditional logic implements a first-fit decreasing heuristic based on the order of encounter. The conflict set `C` is the key mechanism enforcing the non-crossing property within each plane.
* **Notable Implications:**
* **Order-Dependent Outcome:** The final partition `P1, P2` is highly dependent on the order arcs are considered (the `xr`, `xl` loop order). Different orderings could yield different valid partitions or different numbers of unassigned arcs.
* **Optimality:** This is a greedy heuristic, not necessarily an optimal algorithm. It may fail to find a valid 2-page embedding even if one exists, because a poor early assignment could block later ones.
* **Efficiency:** The algorithm has a time complexity of O(n² * |T|) in the worst case, due to the nested loops and the need to check for crossings against all previously placed arcs when constructing set `C`.
