A gráfelméletben az illesztési gráf olyan gráf, amely úgy rajzolható meg egy síkon, hogy minden éle egy hosszúságú szakasz, és az élek nem metszik egymást. Így ennek a gráfnak van beágyazása a síkban egységnyi távolsággráfként és síkgráfként is . Informálisan szólva, egy egyezési gráfot nem metsző egyezésekkel is ki lehet rakni egy sík felületre , innen ered a név [1] .
A gyufaszál-gráfokkal kapcsolatos sok kutatás olyan reguláris gráfokra vonatkozik, amelyekben minden csúcsnak ugyanannyi szomszédja van. Ezt a számot a gráf fokának nevezzük.
Ismeretes, hogy a negyedikig minden fokú egyezési grafikon létezik. Az egy, kettő és három csúcsot tartalmazó teljes gráfok (egy csúcs, egy él és egy háromszög) gyufaszál-gráfok, 0-, 1-, illetve 2-regulárisak. A legkisebb, 3 szabályos gyufaszál gráfot két rombuszmásolat alkotja, amelyek úgy helyezkednek el, hogy a megfelelő csúcsok egységnyi távolságra legyenek. Kettős bipartit fedője egy nyolcszögletű prizma metszéspontokkal rendelkező grafikonja [1] .
1986-ban Heiko Harbort bemutatta az Earl-t, aki megkapta a nevét - Earl of Harbort . 104 élével és 52 csúcsával ez a gráf a legkisebb ismert példa egy 4 szabályos egyezésű gráfra [2] . A grafikon merev [3] .
Lehetetlen, hogy egy szabályos illesztési gráf foka nagyobb legyen négynél [4] .
Amint azt Kurtz és Mazukolo [5] mutatja , a legkisebb 3 szabályos háromszög nélküli gyufaszál gráfnak (körméret ≥ 4) 20 csúcsa van. Ezen kívül bemutatták a legkisebb ismert példát egy 3 szabályos gyufaszál gráfra, amelynek kerülete 5 (180 csúcs).
Annak ellenőrzése, hogy egy adott irányítatlan síkgráf ábrázolható-e matchstick gráfként, NP-nehéz probléma [6] [7]
A különböző (izomorfizmusig) illesztési gráfok száma tíz élig ismert [8] [9] :
1., 1. , 3. , 5. , 12. , 28. , 74. , 207., 633., 2008, …