Good Spanning Tree¶

Select a rooted spanning tree of a fixed plane embedding whose non-tree edges avoid ancestor chords and occur in left, child-tree, and right blocks around every vertex, enabling ordered planar graph drawings and visibility representations.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1945
Origin domain: mathematics
Subdomain: graph drawing
Aliases: Good spanning tree of a plane graph

Core Idea¶

A good spanning tree is a technically constrained rooted spanning tree of a plane graph—a planar graph together with a fixed embedding. Relative to each root-to-vertex tree path, the embedding separates off-path child subtrees into left and right families. The tree is good when no non-tree edge joins the endpoint vertex back to a strict ancestor on that path and when all remaining incident edges occur in three consecutive clockwise blocks: non-tree edges reaching left-side subtrees, tree edges to children, and non-tree edges reaching right-side subtrees.^[1]

The adjective “good” is a defined predicate, not a claim that the tree is short, minimum-weight, balanced, or universally optimal. Its role is to coordinate three structures that an ordinary spanning tree leaves independent: ancestry in the rooted tree, cyclic order in the plane embedding, and placement of the non-tree edges. That compatibility supplies enough order to construct monotone grid drawings and visibility-style representations while controlling crossings and direction changes.^[1]

Embedding is constitutive. A connected planar graph may have an embedding containing a good spanning tree even though another embedding of the same abstract graph has none. Hossain and Rahman prove that every connected planar graph admits a suitable embedding and good spanning tree and give a linear-time construction. Thus existence for the abstract graph means existence of a compatible pair; it does not license erasing the plane embedding from the definition.

Structural Signature¶

Connected planar graph. A spanning tree exists and a crossing-free embedding can be selected.
Fixed plane embedding. Every vertex carries a cyclic order of incident edges.
Rooted spanning tree. All vertices are connected by tree edges with parent, child, ancestor, and descendant relations.
Root-to-vertex path. For each nonroot vertex, its unique tree path from the root supplies the ancestry reference.
Left/right off-path subtrees. Cyclic order around ancestors classifies branches beside the path.
Ancestor-chord exclusion. No non-tree edge from the endpoint returns to a strict ancestor on its root path.
Three-block incidence order. Around the endpoint, left-reaching non-tree edges, child tree edges, and right-reaching non-tree edges form consecutive blocks in that order.
Global compatibility. The local condition holds at every nonroot vertex.
Constructive existence. A suitable embedding-tree pair can be found in linear time for a connected planar graph.
Drawing consequence. The ordered structure supports monotone and visibility representations.

What It Is Not¶

Not any spanning tree of a planar graph. The rooted ancestry and embedding-order conditions are additional.
Not a minimum spanning tree. No edge weights or minimum total cost appear.
Not embedding invariant. Goodness is evaluated for a plane graph, not the abstract graph alone.
Not merely depth-first search. A DFS tree can share ancestor restrictions but does not automatically satisfy the three clockwise incidence blocks.
Not a Schnyder wood. Both support planar drawing, but their orientations, color classes, and axioms differ.
Not a claim of best drawing quality. The predicate enables particular construction guarantees rather than optimizing every aesthetic criterion.

Scope of Application¶

The construct is literal in planar graph drawing and representation algorithms where a rooted tree must mediate between graph connectivity and cyclic embedding order.

Monotone graph drawing. Constructing straight-line drawings in which each vertex pair admits a path monotone in some direction.
Grid drawing. Bounding coordinates for constructive planar representations.
2-visibility representation. Using the tree's ordering to build visibility layouts.
VPG-style representations. Supporting path-intersection constructions for planar graphs.
Planar embedding algorithms. Selecting an embedding compatible with the needed rooted-tree invariant.
Proof certificates. Separating an existence theorem into a checkable embedding plus tree predicate.

Clarity¶

Say whether the graph is planar or already plane, identify the embedding, root, spanning tree, and clockwise convention. For every nonroot vertex, define its root path, the left and right off-path descendant regions, and the three incident sets conventionally called X, Y, and Z. State both conditions: exclusion of non-tree ancestor chords and consecutiveness plus order of the three blocks. Distinguish existence of some suitable embedding from goodness in the supplied embedding. If an algorithmic bound is claimed, state the input representation and output pair.

Manages Complexity¶

Planar drawings are globally constrained: one poorly placed non-tree edge can invalidate a local construction far away. A good spanning tree compresses this interaction into a rooted hierarchy plus a repeated local cyclic-order test. Once the invariant holds, drawing algorithms can process subtrees systematically instead of reconsidering all edges globally. The compression is specialized; most spanning-tree objectives do not need embedding order, and forcing the predicate outside its drawing role adds structure without benefit.

Abstract Reasoning¶

Fix or construct a plane embedding of the connected planar graph.
Choose a root and spanning tree and compute ancestor/descendant relations.
For each nonroot vertex, trace its root path.
Use cyclic incidence order to partition off-path descendant subtrees into left and right groups.
Reject a candidate tree if a non-tree edge joins the vertex to a strict path ancestor.
Check that left-reaching non-tree, child-tree, and right-reaching non-tree edges form consecutive ordered blocks.
If the predicate fails, alter the tree or embedding rather than relabel the same structure.
Consume the certified pair in the drawing or visibility construction.
Keep drawing guarantees bounded to those proved from the invariant.

Knowledge Transfer¶

The strict parent is Hierarchy: rooting the spanning tree organizes graph vertices into parent-child levels and makes ancestor relations available for every local condition. Connectedness and Network Traversal are close primes, while Tree (Graph Theory) and Planarity are accepted domain-specific neighbors. The named construct remains graph-drawing-specific because cyclic embedding order and non-tree edge blocks are constitutive.

Examples¶

Canonical¶

For a vertex on a root path, remove the parent edge from the cyclic list of incident edges. If the remaining edges appear as a block of non-tree edges into left-side ancestor subtrees, then a block of edges to children of the vertex, then a block of non-tree edges into right-side subtrees—and no non-tree edge returns directly to an ancestor on the path—the local predicate holds. Every nonroot vertex must pass the same test.^[1]

Mapped back: plane embedding + rooted spanning hierarchy → path-relative left/right regions → ordered incident-edge blocks → good-tree certificate.

Applied / In Practice¶

A drawing algorithm receives only an abstract connected planar graph. It first constructs the particular embedding and rooted spanning tree guaranteed by the existence algorithm, verifies the good-tree conditions, and then uses the subtree order to place vertices for a monotone grid drawing. Reusing an arbitrary preexisting embedding would be unjustified because not every embedding contains a good spanning tree.

Mapped back: abstract planar graph → compatible embedding/tree construction → local certificate → monotone drawing algorithm.

Structural Tensions¶

Abstract planarity vs. fixed embedding. A planar graph admits many cyclic orders. Diagnostic: Is goodness asserted for this embedding or for existence of another?
Local test vs. global guarantee. Conditions are checked vertexwise but constrain a whole drawing. Diagnostic: Has every nonroot vertex been checked under one consistent root and embedding?
Tree edges vs. non-tree edges. The spanning hierarchy simplifies connectivity while omitted edges carry the difficult geometry. Diagnostic: Are all non-tree incidences classified?
Technical goodness vs. optimization language. “Good” can be mistaken for shortest or best. Diagnostic: Are the two defining conditions stated rather than an informal quality claim?
Autonomous graph-drawing construct vs. generic hierarchy. Hierarchy travels; embedding-order blocks define this residual. Diagnostic: Does the candidate retain the plane graph and non-tree-edge constraints?

Structural–Framed Character¶

Good spanning tree is strongly structural after a plane embedding is fixed. The embedding is a chosen representation of an abstract planar graph, but cyclic orders and predicate satisfaction are then exact. “Good” is not evaluative in this context. Algorithmic utility depends on the targeted drawing model, which supplies a limited engineering frame around the mathematics.

Structural Core vs. Domain Accent¶

The skeleton is a rooted hierarchy plus omitted relations and a local ordering constraint that supplies a global constructive certificate. The accent is spanning trees of plane graphs, clockwise incidence order, ancestor paths, non-tree edges, and drawing representations. Removing it yields Hierarchy or a generic constrained tree.

Hierarchy is the strict prime parent because the rooted spanning tree creates the ancestor/descendant level structure used by every defining condition. Connectedness is presupposed, and Tree (Graph Theory) is the closest domain-specific taxonomic neighbor, but the frozen protocol requires a prime endpoint.

The prospective workspace queue contains one strict upward edge to prime:hierarchy. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Good Spanning Tree Domain-specific

Parents (1) — more general patterns this builds on

Good Spanning Tree is a kind of Hierarchy Prime

Hierarchy is the strict prime parent because the rooted spanning tree creates the ancestor/descendant level structure used by every defining condition.

Hierarchy paths (4) — routes to 4 parentless roots

Good Spanning Tree → Hierarchy → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Show alternative paths (3)

Neighborhood in Abstraction Space¶

Good Spanning Tree sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Multitree — 0.83
Tree (Graph Theory) — 0.81
Cyclomatic number — 0.79
Dually chordal graph — 0.79
Cubic Graph — 0.79

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Spanning tree. Any connected acyclic spanning subgraph, without the good-tree embedding constraints.
Minimum spanning tree. Optimizes edge weight.
Depth-first search tree. Arises from a traversal order and satisfies different non-tree-edge properties.
Schnyder wood. A different orientation/color structure for planar graphs.
SPQR tree. Decomposes a biconnected graph by separation pairs.
Planar embedding. Supplies cyclic order but no spanning-tree choice.

References¶

[1] Md. Iqbal Hossain and Md. Saidur Rahman, “Good Spanning Trees in Graph Drawing,” Theoretical Computer Science 607, part 2 (2015): 149–165, https://doi.org/10.1016/j.tcs.2015.09.004. registry ↩a ↩b ↩c