カクタスグラフ
カクタスは平面グラフであり、外平面グラフ(outerplanar graph)でもある。また、疑似木(pseudotree)はカクタスである。全てのブロックが単純閉路または辺のいずれかである場合にのみ、非単純グラフ(連結な多重グラフ)はカクタスである。
各連結成分がカクタスである族は、「グラフの細分に対して閉じている」といえる。つまり、任意のカクタスの任意の細分はカクタスである。このグラフの族は、たった一つの禁断マイナーで特徴付けられ、完全グラフK4から1辺のみを除去した4頂点ダイヤモンドグラフがカクタスの禁断グラフである。
カクタスグラフ(もしくは単にカクタス、カクタス木)は任意の2つの単純閉路が2つ以上の共通頂点を持たない連結グラフである。別の言い方をすれば、全ての辺が高々1つの閉路にしか含まれない連結グラフや、(非自明だが)全てのブロック(切断点のない最大部分グラフ)が閉路または辺となる連結グラフであると言える。
↑ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), “Efficient algorithms for the weighted 2-center problem in a cactus graph”, Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science, 3827, Springer-Verlag, pp. 693–703, doi:10.1007/11602613_70
↑ Zmazek, Blaz; Zerovnik, Janez (2005), “Estimating the traffic on weighted cactus networks in linear time”, Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, doi:10.1109/IV.2005.48, ISBN 0-7695-2397-8
↑ Korneyenko, N. M. (1994), “Combinatorial algorithms on a class of graphs”, Discrete Applied Mathematics 54 (2–3): 215–217, doi:10.1016/0166-218X(94)90022-1.
↑ Nishi, Tetsuo; Chua, Leon O.