Overview
Boyer-Myrvold Planarity Test is a planarity testing method for planarity embedding. It works by incrementally maintaining embedding constraints during depth-first traversal.
SpecializedSource checked
Boyer-Myrvold Planarity Test
Boyer-Myrvold Planarity Test addresses planarity embedding by incrementally maintaining embedding constraints during depth-first traversal.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Advanced
- Family
- Planarity Testing
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 4
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
planarity embeddingplanarity testingdepth-first searchvisibility orderinggraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use Boyer-Myrvold Planarity Test when solving planarity embedding and you want to benefit from incrementally maintaining embedding constraints during depth-first traversal.
- Choose it when O((V + E) log V) average/worst-case time and O(V + E) memory match your workload profile.
- Prefer it over Hopcroft-Tarjan Planarity Test or Planar Embedding when the problem structure favors planarity embedding.
When Not to Use
- Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
- Avoid when a simpler traversal gives the same information with less bookkeeping.
What It Does
- Computes planarity embedding within Planarity Testing workloads (O((V + E) log V) time, O(V + E) space).
- Works by incrementally maintaining embedding constraints during depth-first traversal.
- Maintains key invariants across planarity embedding, planarity testing, depth-first search.
Use Cases
- Production and research workloads requiring planarity embedding via incrementally maintaining embedding constraints during depth-first traversal.
- Planarity Testing pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Hopcroft-Tarjan Planarity Test and Planar Embedding when tuning planarity embedding.
Inputs
- Undirected graph G = (V, E)
Outputs
- Boolean planarity verdict
- Combinatorial planar embedding (cyclic edge ordering) or Kuratowski subgraph
Pseudocode
- 1.Construct the graph representation G = (V, E) and initialize auxiliary structures for planarity embedding (planarity testing).
- 2.Seed the initial frontier, partition, or residual capacities according to Boyer-Myrvold Planarity Test's invariants.
- 3.Iteratively process vertices or edges by incrementally maintaining embedding constraints during depth-first traversal.
- 4.Maintain structural invariants (planarity embedding, planarity testing, depth-first search) and prune or contract resolved subproblems.
- 5.Extract and return the final planarity embedding structure from the converged graph state.
Canonical Example
- Input
- Undirected graph G = (V, E) configured for a representative planarity embedding test case
- Output
- Boolean planarity verdict satisfying Boyer-Myrvold Planarity Test invariants
- Explanation
- Boyer-Myrvold Planarity Test processes the input by incrementally maintaining embedding constraints during depth-first traversal, tracking planarity embedding and planarity testing to produce the verified planarity embedding result.
Implementation Notes
- Represent vertices and edges explicitly before optimizing storage.
- Keep graph direction, weights, and multiedges clear in tests.
- Record tie-breaking when multiple valid outputs exist.
Common Pitfalls
- Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
- Forgetting disconnected components or isolated vertices.
- Letting tie-breaking hide nondeterministic output in tests.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow incrementally maintaining embedding constraints during depth-first traversal on a small planarity embedding example.
Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for planarity embedding (planarity testing).
graph-traversal-mechanismNotes
Boyer-Myrvold Planarity Test operates in O((V + E) log V) time and O(V + E) space within the Planarity Testing family. Often compared with Hopcroft-Tarjan Planarity Test and Planar Embedding.
Sources (3)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Boyer-Myrvold Planarity Test's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Boyer-Myrvold Planarity Test in the graph, flow, matching, and combinatorial optimization benchmark area.
Open sourceBoyer-Myrvold Planarity
PaperReference for the edge-addition linear-time planarity and embedding method.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageBoyer-Myrvold Planarity Test uses Hopcroft-Tarjan Planarity Test as a subroutine, representation, or supporting idea while incrementally maintaining embedding constraints during depth-first traversal.
UsesPlanar Embedding
Boyer-Myrvold Planarity Test uses Planar Embedding as a subroutine, representation, or supporting idea while incrementally maintaining embedding constraints during depth-first traversal.
Related Algorithms
Tags
GraphTraversalConstraint Solving