マッチ棒グラフ

3-通常の胴回り-5マッチ棒グラフ
3-通常の胴回り-5マッチ棒グラフ
頂点	54
エッジ	81
胴回り	5
	グラフとパラメータの表

ハーバースグラフ
ハーバースグラフ
頂点	52
エッジ	104
半径	6
直径	9
胴回り	3
	グラフとパラメータの表

交差なしで描画できる、長さ1の辺を持つグラフ

数学の一分野である幾何学的グラフ理論において、マッチ棒グラフとは、平面上に、辺が互いに交差しない長さ1の線分であるように描くことができるグラフである。つまり、単位距離グラフであると同時に平面グラフでもある埋め込みを持つグラフである。このため、マッチ棒グラフは平面単位距離グラフとも呼ばれる。^{[1]非公式には、マッチ棒グラフは平面上に交差しない}マッチ棒を置くことで作ることができるため、この名前が付けられている。^[2]

通常のマッチ棒グラフ

マッチ棒グラフに関する研究の多くは、各頂点に同数の隣接頂点を持つ正則グラフを対象としています。この数はグラフの次数と呼ばれます。

正則マッチ棒グラフの次数は0、1、2、3、または4です。1、2、3頂点（1つの頂点、1つの辺、三角形）を持つ完全グラフはすべてマッチ棒グラフであり、それぞれ0-正則、1-正則、2-正則です。最小の 3-正則マッチ棒グラフは、ダイヤモンドグラフを2つコピーし、対応する頂点が互いに単位距離になるように配置することで形成されます。その二部二重被覆は、8-交差プリズムグラフです。^[2]

1986年、ハイコ・ハーバースはハーバース・グラフとして知られるグラフを発表しました。このグラフは104辺と52頂点を持ち、現在知られている4-正則マッチ棒グラフの中で最も小さい例です。^[3]これは剛体グラフです。^[4]

4-正則マッチ棒グラフは、少なくとも20個の頂点を持つ。^[5] 4-正則マッチ棒グラフの例は、頂点数が53、55、56、58、59、61、62を除く、52以上のすべての頂点数について現在知られている。54、57、65、67、73、74、77、85の頂点を持つグラフは2016年に初めて公開された。52、54、57、60、64の頂点を持つグラフの例は1つしか知られていない。これら5つのグラフのうち、60頂点を持つグラフだけが柔軟で、他の4つは固定である。^[6] ^[7]

通常のマッチ棒グラフの次数が4を超えることは不可能である。^[5]さらに強く主張すると、すべての-頂点マッチ棒グラフの頂点の次数は4以下である。^[8]三角形のない最小の3-通常のマッチ棒グラフ（内周≥4）は、KurzとMazzuoccoloによって証明されたように、20頂点を持つ。^[9] 内周5の3-通常のマッチ棒グラフの既知の最小の例は54頂点であり、2019年にMike Winklerによって初めて提示された。^[10] $n$ $\Omega ({\sqrt {n}})$

マッチ棒グラフが頂点上で持つことができる辺の最大数はである。^[11] $n$ $\left\lfloor 3n-{\sqrt {12n-3}}\right\rfloor$

計算の複雑さ

与えられた無向平面グラフがマッチ棒グラフとして実現できるかどうかをテストすることはNP困難である。 ^[12]^[13]より正確には、この問題は実数の存在理論に対して完全である。^[14] Kurz (2011) は、グラフがマッチ棒グラフであるための簡単にテストできる必要条件をいくつか提供しているが、これらは十分な条件ではない。グラフは Kurz のテストに合格しても、マッチ棒グラフではない可能性がある。^[15]

マッチ棒グラフにハミルトン閉路があるかどうかを判断することは、グラフの頂点がすべて整数座標を持ち、それが問題への入力の一部として与えられた場合でも、NP完全である。 ^[16]

組み合わせ列挙

異なる（非同型）マッチ棒グラフの数は、1、2、3、… 最大 13 辺まで知られています。それらは次のとおりです。

1、1、3、5、12、28、74、207、633、2008、6774、23868、87667（OEISの配列A066951）^[17]^[18]

たとえば、3 本のマッチ棒で作成できる 3 つの異なるグラフは、爪グラフ、三角形グラフ、および 3 辺パスグラフです。

グラフの特別なクラス

辺の長さの均一性は長い間グラフ描画において望ましい特性であると考えられてきました^[19]。また、平面グラフの特定のクラスは常に完全に均一な辺で描画することができます。

あらゆる樹木は、その葉の辺を無限光線に置き換えたとすれば、平面を交差のない凸多角形領域に分割するように描くことができる。このような描画では、各辺の長さを任意に変更しても、傾きを変えなければ、描画は平面のままである。特に、すべての辺の長さを等しくすることで、任意の樹木をマッチ棒グラフとして実現することができる。^[20]

同様の性質は、平面グラフであるスクエアグラフにも当てはまる。スクエアグラフは、平面上に描画されるグラフであり、すべての境界面が四角形であり、すべての頂点が境界のない面上にあるか、少なくとも4つの隣接頂点を持つ。これらのグラフは、すべての面が平行四辺形で描画され、互いに平行な辺のサブセットを同時に長くしたり短くしたりして、すべての辺の長さが同じになるようにすれば、交差は発生しない。これにより、辺がすべて同じ長さになるように正規化し、任意のスクエアグラフをマッチ棒グラフとして実現することが可能になる。^[21]

参考文献

^ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008)、「平面単位距離グラフと平面単位距離補集合」、離散数学、308 (10): 1973– 1984、doi : 10.1016/j.disc.2007.04.050、MR 2394465
^ ab Weisstein、Eric W.、「マッチスティックグラフ」、MathWorld{{cite web}}: CS1 メンテナンス: 上書き設定 (リンク)
^ Harborth, Heiko (1994), "Match sticks in the plane", Guy, RK; Woodrow, RE (eds.), The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 , Washington, DC: Mathematical Association of America , pp. 281– 288引用元：Weisstein, Eric W.、「マッチ棒グラフ」、MathWorld{{cite web}}: CS1 メンテナンス: 上書き設定 (リンク)
^ Gerbracht, Eberhard H.-A. (2011)、「ハーバースグラフのシンボルクランチング」、応用数学の進歩、47 (2): 276– 281、doi : 10.1016/j.aam.2010.09.003、MR 2803803詳細については、Gerbracht, Eberhard H.-A. (2006) のプレプリント「Harborth Graph の座標の最小多項式」arXiv : math/0609360を参照してください。{{cite arXiv}}: CS1 メンテナンス: 上書き設定 (リンク)。
^ ab Kurz, Sascha; Pinchasi, Rom (2011)、「Regular matchstick graphs」、American Mathematical Monthly、118 (3): 264– 267、arXiv : 1401.4372、doi :10.4169/amer.math.monthly.118.03.264、MR 2800336、S2CID 866740 。
^ ウィンクラー、マイク；ディンケラッカー、ピーター；フォーゲル、ステファン（2017）「新しい極小 $（4;$ $n$ $）$ -正則マッチ棒グラフ」、ジオムビナトリクス、27：26-44、arXiv：1604.07134。
^ ウィンクラー、マイク；ディンケラッカー、ピーター；フォーゲル、ステファン（2017）「4-正則マッチ棒グラフの存在について」arXiv：1705.00293。
^ Lavollée, Jérémy; Swanepoel, Konrad J. (2023)、「マッチ棒グラフにおける低次頂点の数」、The Australasian Journal of Combinatorics、85 : 92–99、arXiv : 2206.03956、MR 4515475
^ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010)、「与えられた内周を持つ3-regular matchstick graphs」、Geombinatorics、19 : 156–175、arXiv : 1401.4360。
^ ウィンクラー、マイク; ディンケラッカー、ピーター; フォーゲル、ステファン (2020)、「54個の頂点からなる内周5の3正則マッチ棒グラフ」、ジオムビナトリクス、29 : 116–121、arXiv : 1903.04304。
^ Lavollée, Jérémy; Swanepoel, Konrad (2023年8月18日)、「マッチ棒グラフの辺の数の厳密な境界」、Discrete & Computational Geometry、72 (4): 1530– 1544、arXiv : 2209.09800、doi : 10.1007/s00454-023-00530-z、ISSN 1432-0444
^ Eades, Peter ; Wormald, Nicholas C. (1990)、「固定辺長グラフ描画はNP困難である」、Discrete Applied Mathematics、28 (2): 111– 134、doi : 10.1016/0166-218X(90)90110-X。
^ Cabello, Sergio; Demaine, Erik D .; Rote, Günter (2007)、「指定された辺長を持つグラフの平面埋め込み」(PDF)、Journal of Graph Algorithms and Applications、11 (1): 259– 276、doi :10.7155/jgaa.00145。
^ Abel, Zachary; Demaine, Erik D .; Demaine, Martin L .; Eisenstat, Sarah; Lynch, Jayson; Schardl, Tao B. (2016)「Who needs crossings? Hardness of plane graph rigidity」、Fekete, Sándor; Lubiw, Anna (eds.)、32nd International Symposium on Computational Geometry (SoCG 2016)、Leibniz International Proceedings in Informatics (LIPIcs)、第51巻、ダグストゥール、ドイツ：Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik、pp. 3:1–3:15、doi：10.4230/LIPIcs.SoCG.2016.3、ISBN 978-3-95977-009-5。
^ Kurz, Sascha (2011)、「平面非単位距離グラフの高速認識」、Geombinatorics、21 (1): 25– 33、arXiv : 1401.4375、MR 2858668。
^ イタイ、アロン;パパディミトリウ、クリストス H.;シュワルクフィター、ジェイミー・ルイス (1982)、「グリッドグラフにおけるハミルトンパス」、SIAM Journal on Computing、11 (4): 676– 686、CiteSeerX 10.1.1.383.1078、doi :10.1137/0211056、MR 0677661 。
^ Salvia, Raffaele (2013)、「マッチ棒グラフのカタログ」、arXiv : 1303.5965 [math.CO]{{cite arXiv}}: CS1 メンテナンス: 上書き設定 (リンク)
^ Vaisse, Alexis (2023), 最大13辺のマッチ棒グラフ
^ Fruchterman, Thomas MJ; Reingold, Edward M. (1991)、「力指向配置によるグラフ描画」、ソフトウェア：実践と経験、21 (11)、Wiley: 1129– 1164、doi :10.1002/spe.4380211102、S2CID 31468174 。
^ Carlson, Josiah; Eppstein, David (2006)、「凸面と最適角度を持つ木」、Kaufmann, Michael; Wagner, Dorothea (編)、Proceedings of the 14th International Symposium on Graph Drawing、Lecture Notes in Computer Science、vol. 4372、Springer-Verlag、pp. 77– 88、arXiv : cs.CG/0607113、doi : 10.1007 /978-3-540-70904-6_9、ISBN 978-3-540-70903-9、MR 2393907、S2CID 12598338。
^ Eppstein, David; Wortman, Kevin A. (2011), 「面対称描画の最適角度解像度」、Journal of Graph Algorithms and Applications、15 (4): 551– 564、arXiv : 0907.5474、doi :10.7155/jgaa.00238、S2CID 10356432 。

[1] Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008)、「平面単位距離グラフと平面単位距離補集合」、離散数学、308 (10): 1973– 1984、doi : 10.1016/j.disc.2007.04.050、MR 2394465

[mmg-2] Weisstein、Eric W.、「マッチスティックグラフ」、MathWorld{{cite web}}: CS1 メンテナンス: 上書き設定 (リンク)

[mhg-3] Harborth, Heiko (1994), "Match sticks in the plane", Guy, RK; Woodrow, RE (eds.), The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 , Washington, DC: Mathematical Association of America , pp. 281– 288引用元：Weisstein, Eric W.、「マッチ棒グラフ」、MathWorld{{cite web}}: CS1 メンテナンス: 上書き設定 (リンク)

[4] Gerbracht, Eberhard H.-A. (2011)、「ハーバースグラフのシンボルクランチング」、応用数学の進歩、47 (2): 276– 281、doi : 10.1016/j.aam.2010.09.003、MR 2803803詳細については、Gerbracht, Eberhard H.-A. (2006) のプレプリント「Harborth Graph の座標の最小多項式」arXiv : math/0609360を参照してください。{{cite arXiv}}: CS1 メンテナンス: 上書き設定 (リンク)。

[Kurz,Pinchasi,2011-5] Kurz, Sascha; Pinchasi, Rom (2011)、「Regular matchstick graphs」、American Mathematical Monthly、118 (3): 264– 267、arXiv : 1401.4372、doi :10.4169/amer.math.monthly.118.03.264、MR 2800336、S2CID 866740 。

[6] ウィンクラー、マイク；ディンケラッカー、ピーター；フォーゲル、ステファン（2017）「新しい極小 $（4;$ $n$ $）$ -正則マッチ棒グラフ」、ジオムビナトリクス、27：26-44、arXiv：1604.07134。

[7] ウィンクラー、マイク；ディンケラッカー、ピーター；フォーゲル、ステファン（2017）「4-正則マッチ棒グラフの存在について」arXiv：1705.00293。

[8] Lavollée, Jérémy; Swanepoel, Konrad J. (2023)、「マッチ棒グラフにおける低次頂点の数」、The Australasian Journal of Combinatorics、85 : 92–99、arXiv : 2206.03956、MR 4515475

[9] Kurz, Sascha; Mazzuoccolo, Giuseppe (2010)、「与えられた内周を持つ3-regular matchstick graphs」、Geombinatorics、19 : 156–175、arXiv : 1401.4360。

[10] ウィンクラー、マイク; ディンケラッカー、ピーター; フォーゲル、ステファン (2020)、「54個の頂点からなる内周5の3正則マッチ棒グラフ」、ジオムビナトリクス、29 : 116–121、arXiv : 1903.04304。

[11] Lavollée, Jérémy; Swanepoel, Konrad (2023年8月18日)、「マッチ棒グラフの辺の数の厳密な境界」、Discrete & Computational Geometry、72 (4): 1530– 1544、arXiv : 2209.09800、doi : 10.1007/s00454-023-00530-z、ISSN 1432-0444

[12] Eades, Peter ; Wormald, Nicholas C. (1990)、「固定辺長グラフ描画はNP困難である」、Discrete Applied Mathematics、28 (2): 111– 134、doi : 10.1016/0166-218X(90)90110-X。

[13] Cabello, Sergio; Demaine, Erik D .; Rote, Günter (2007)、「指定された辺長を持つグラフの平面埋め込み」(PDF)、Journal of Graph Algorithms and Applications、11 (1): 259– 276、doi :10.7155/jgaa.00145。

[14] Abel, Zachary; Demaine, Erik D .; Demaine, Martin L .; Eisenstat, Sarah; Lynch, Jayson; Schardl, Tao B. (2016)「Who needs crossings? Hardness of plane graph rigidity」、Fekete, Sándor; Lubiw, Anna (eds.)、32nd International Symposium on Computational Geometry (SoCG 2016)、Leibniz International Proceedings in Informatics (LIPIcs)、第51巻、ダグストゥール、ドイツ：Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik、pp. 3:1–3:15、doi：10.4230/LIPIcs.SoCG.2016.3、ISBN 978-3-95977-009-5。

[15] Kurz, Sascha (2011)、「平面非単位距離グラフの高速認識」、Geombinatorics、21 (1): 25– 33、arXiv : 1401.4375、MR 2858668。

[16] イタイ、アロン;パパディミトリウ、クリストス H.;シュワルクフィター、ジェイミー・ルイス (1982)、「グリッドグラフにおけるハミルトンパス」、SIAM Journal on Computing、11 (4): 676– 686、CiteSeerX 10.1.1.383.1078、doi :10.1137/0211056、MR 0677661 。

[17] Salvia, Raffaele (2013)、「マッチ棒グラフのカタログ」、arXiv : 1303.5965 [math.CO]{{cite arXiv}}: CS1 メンテナンス: 上書き設定 (リンク)

[18] Vaisse, Alexis (2023), 最大13辺のマッチ棒グラフ

[19] Fruchterman, Thomas MJ; Reingold, Edward M. (1991)、「力指向配置によるグラフ描画」、ソフトウェア：実践と経験、21 (11)、Wiley: 1129– 1164、doi :10.1002/spe.4380211102、S2CID 31468174 。

[20] Carlson, Josiah; Eppstein, David (2006)、「凸面と最適角度を持つ木」、Kaufmann, Michael; Wagner, Dorothea (編)、Proceedings of the 14th International Symposium on Graph Drawing、Lecture Notes in Computer Science、vol. 4372、Springer-Verlag、pp. 77– 88、arXiv : cs.CG/0607113、doi : 10.1007 /978-3-540-70904-6_9、ISBN 978-3-540-70903-9、MR 2393907、S2CID 12598338。

[21] Eppstein, David; Wortman, Kevin A. (2011), 「面対称描画の最適角度解像度」、Journal of Graph Algorithms and Applications、15 (4): 551– 564、arXiv : 0907.5474、doi :10.7155/jgaa.00238、S2CID 10356432 。