SPQR Tree

Author

Eric W. Weisstein
July 29, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/SPQRTree.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/SPQRTree.html.

\[Copyright]2026 Wolfram Research, Inc. except for portions noted otherwise

Illustration

The diagram shows a graph together with an SPQR tree whose Q-nodes are omitted. Solid lines are real edges and dashed orange lines are virtual edges.

spqrTreeFigure = Module[
		{
			realEdgeColor = StandardGray,
			virtualEdgeColor = LightDarkSwitched[RGBColor[0.88, 0.38, 0.12]],
			vertexColor = LightDarkSwitched[RGBColor[0.12, 0.42, 0.68]],
			treeColor = LightDarkSwitched[RGBColor[0.48, 0.60, 0.68]],
			boxEdgeColor = LightDarkSwitched[RGBColor[0.76, 0.80, 0.82]],
			boxFillColor = LightDarkSwitched[RGBColor[0.98, 0.985, 0.99]],
			branchCenters = {-2.25, 0, 2.25},
			branchCoordinates,
			branchEdges,
			graphPanel,
			treePanel,
			vertex,
			realEdges,
			virtualEdges,
			nodeBox,
			nodeLabel,
			sSkeleton,
			pSkeleton,
			rSkeleton
		},
		vertex[p_] := {
			EdgeForm[{LightDarkSwitched[White], AbsoluteThickness[1.2]}],
			vertexColor,
			Disk[p, 0.095]
		};
		realEdges[coordinates_, edges_] := {
			realEdgeColor,
			AbsoluteThickness[2.2],
			Line[Map[coordinates[[#]] &, edges]]
		};
		virtualEdges[coordinates_, edges_] := {
			virtualEdgeColor,
			AbsoluteThickness[2.6],
			Dashing[{0.018, 0.012}],
			Line[Map[coordinates[[#]] &, edges]]
		};
		branchCoordinates[c_] := {
			{c, 1.65},
			{c - 0.75, 1.05},
			{c, 0.55},
			{c + 0.75, 1.05},
			{c, -0.55},
			{c - 0.75, -1.05},
			{c, -1.65},
			{c + 0.75, -1.05}
		};
		branchEdges = {
			{1, 2}, {2, 3}, {3, 4}, {4, 1},
			{7, 6}, {6, 5}, {5, 8}, {8, 7},
			{3, 5}, {2, 6}, {4, 8}
		};
		graphPanel = Graphics[
			{
				realEdgeColor,
				AbsoluteThickness[2.2],
				Map[
					Function[c,
						With[{coordinates = branchCoordinates[c]},
							{
								Line[Map[coordinates[[#]] &, branchEdges]],
								Line[{{0, 3.0}, coordinates[[1]]}],
								Line[{coordinates[[7]], {0, -3.0}}]
							}
						]
					],
					branchCenters
				],
				Map[vertex, Join[{{0, 3.0}, {0, -3.0}}, Flatten[Map[branchCoordinates, branchCenters], 1]]],
				Inset[
					Style["graph G", 17, Bold, LightDarkSwitched[GrayLevel[0.18]], FontFamily -> "Times"],
					{0, 3.55}
				]
			}
		];
		nodeBox[{x_, y_}, {w_, h_}] := {
			EdgeForm[{boxEdgeColor, AbsoluteThickness[1.6]}],
			boxFillColor,
			Rectangle[{x - w/2, y - h/2}, {x + w/2, y + h/2}, RoundingRadius -> 0.12]
		};
		nodeLabel[label_, {x_, y_}, {w_, h_}] := Inset[
			Style[
				label,
				17,
				Bold,
				LightDarkSwitched[RGBColor[0.25, 0.32, 0.36]],
				FontFamily -> "Times"
			],
			{x - w/2 + 0.20, y + h/2 - 0.18}
		];
		pSkeleton[{x_, y_}] := Module[{coordinates},
			coordinates = {{x, y + 0.28}, {x, y - 0.28}};
			{
				virtualEdgeColor,
				AbsoluteThickness[2.4],
				Dashing[{0.018, 0.012}],
				BezierCurve[{coordinates[[1]], {x - 0.28, y}, coordinates[[2]]}],
				Line[coordinates],
				BezierCurve[{coordinates[[1]], {x + 0.28, y}, coordinates[[2]]}],
				Map[vertex, coordinates]
			}
		];
		sSkeleton[{x_, y_}] := Module[{coordinates},
			coordinates = {
				{x - 0.34, y + 0.25},
				{x + 0.34, y + 0.25},
				{x + 0.34, y - 0.25},
				{x - 0.34, y - 0.25}
			};
			{
				realEdges[coordinates, {{1, 4}, {2, 3}}],
				virtualEdges[coordinates, {{1, 2}, {4, 3}}],
				Map[vertex, coordinates]
			}
		];
		rSkeleton[{x_, y_}] := Module[{coordinates},
			coordinates = {
				{x - 0.46, y + 0.34},
				{x + 0.46, y + 0.34},
				{x + 0.46, y - 0.34},
				{x - 0.46, y - 0.34},
				{x - 0.20, y + 0.15},
				{x + 0.20, y + 0.15},
				{x + 0.20, y - 0.15},
				{x - 0.20, y - 0.15}
			};
			{
				realEdges[
					coordinates,
					{
						{2, 3}, {3, 4}, {4, 1},
						{5, 6}, {6, 7}, {7, 8}, {8, 5},
						{1, 5}, {2, 6}, {3, 7}, {4, 8}
					}
				],
				virtualEdges[coordinates, {{1, 2}}],
				Map[vertex, coordinates]
			}
		];
		treePanel = Graphics[
			{
				Inset[
					Style[
						"SPQR tree and skeletons",
						17,
						Bold,
						LightDarkSwitched[GrayLevel[0.18]],
						FontFamily -> "Times"
					],
					{0, 3.55}
				],
				treeColor,
				AbsoluteThickness[3.0],
				Line[{{0, 2.05}, {-2.25, 1.25}}],
				Line[{{0, 2.05}, {0, 1.25}}],
				Line[{{0, 2.05}, {2.25, 1.25}}],
				Line[{{-2.25, 0.55}, {-2.25, -1.20}}],
				Line[{{0, 0.55}, {0, -1.20}}],
				Line[{{2.25, 0.55}, {2.25, -1.20}}],
				nodeBox[{0, 2.45}, {1.20, 1.05}],
				nodeLabel["P", {0, 2.45}, {1.20, 1.05}],
				pSkeleton[{0, 2.42}],
				Map[nodeBox[#, {1.45, 1.15}] &, {{-2.25, 0.95}, {0, 0.95}, {2.25, 0.95}}],
				Map[nodeLabel["S", #, {1.45, 1.15}] &, {{-2.25, 0.95}, {0, 0.95}, {2.25, 0.95}}],
				Map[sSkeleton, {{-2.25, 0.90}, {0, 0.90}, {2.25, 0.90}}],
				Map[nodeBox[#, {1.65, 1.45}] &, {{-2.25, -1.80}, {0, -1.80}, {2.25, -1.80}}],
				Map[nodeLabel["R", #, {1.65, 1.45}] &, {{-2.25, -1.80}, {0, -1.80}, {2.25, -1.80}}],
				Map[rSkeleton, {{-2.25, -1.84}, {0, -1.84}, {2.25, -1.84}}],
				Inset[
					LineLegend[
						{
							Directive[realEdgeColor, AbsoluteThickness[2.2]],
							Directive[virtualEdgeColor, AbsoluteThickness[2.6], Dashing[{0.08, 0.05}]]
						},
						{
							Style["real edge", 12, FontFamily -> "Times"],
							Style["virtual edge", 12, FontFamily -> "Times"]
						},
						LegendLayout -> "Row"
					],
					{0, -3.0}
				]
			}
		];
		GraphicsRow[{graphPanel, treePanel}]
	]

Source

The layout is adapted from a public-domain diagram by David Eppstein, November 10, 2009: https://commons.wikimedia.org/wiki/File:SPQR_tree.svg.

G. Di Battista and R. Tamassia, "On-Line Maintenance of Triconnected Components with SPQR-Trees," Algorithmica 15 (1996), 302-318. https://doi.org/10.1007/BF01961541.