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: v3 · 2026-09-19 · History
Domain-specific #: 1945
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Drawing → Mathematics
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.

How would you explain it like I'm…

The Tidy Tree Rule

Imagine dots on paper joined by lines that never cross. You pick one starting dot and choose some lines so you can walk from it to every dot, like branches of a tree. The tree is called 'good' when, at every dot, the other lines around it sit in a tidy order: some on the left side, then the branches, then some on the right side. 'Good' here is just the name of this tidy rule, not 'shortest' or 'best.'

Left-Middle-Right Tree Rule

Mathematicians study networks of dots and lines drawn flat so no lines cross. A spanning tree picks some of those lines so that every dot is connected with no loops, starting from a root dot. A good spanning tree follows special rules. Around each dot, the leftover non-tree lines must not go straight back to the dot's ancestors, and the lines must come in order going clockwise: leftover lines to the left side, then lines to its children, then leftover lines to the right side. "Good" here does not mean shortest or best. It is just the name for this tidy arrangement, which helps make neat drawings. Whether a tree is good depends on exactly how the network is drawn.

Embedding-Compatible Rooted Spanning Tree

A good spanning tree is a rooted spanning tree of a plane graph, meaning a planar graph together with a fixed way of drawing it in the plane. For each path from the root down to a vertex, the drawing splits the other subtrees into a left family and a right family. The tree is good when two things hold. First, no non-tree edge joins the vertex back to a strict ancestor on that path. Second, the vertex's remaining edges appear in three consecutive clockwise blocks: non-tree edges to left subtrees, tree edges to children, then non-tree edges to right subtrees. Unlike a minimum spanning tree, "good" is not about weight or optimality. It makes tree ancestry, the drawing's edge order and the extra edges fit together, which is useful for building monotone grid drawings. The same abstract graph drawn differently might have no good spanning tree, so the drawing is part of the definition.

Let G be a plane graph, a planar graph with a fixed embedding, and T a spanning tree rooted at r. For any vertex v, the root-to-v path in T splits the off-path subtrees into left and right families, determined by the embedding. T is a good spanning tree when, for each such path, no non-tree edge joins v to a strict ancestor on the path. In addition, the edges incident to v that remain must occur in three consecutive clockwise blocks: non-tree edges into left-side subtrees, tree edges to v's children, and non-tree edges into right-side subtrees. "Good" is a defined predicate and does not mean short, minimum-weight or balanced. The point is to coordinate three structures an arbitrary spanning tree leaves independent: rooted ancestry, cyclic rotation order, and the placement of non-tree edges. That coordination supports constructing monotone grid drawings and visibility-style representations with controlled crossings and bends. The embedding is constitutive, since one embedding of a graph may admit a good spanning tree while another does not. Hossain and Rahman showed that every connected planar graph has some embedding with a good spanning tree, constructible in linear time.

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.

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.

Relationships to Other Abstractions¶

Current abstraction Good Spanning Tree Domain-specific

Parents (1) — outgoing typed relations

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 → is a kind of Hierarchy → is a kind of Network

Show alternative paths (3)

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25