Találkozik egyetlen túra
A G négyzete a G csúcshalmazával rendelkező olyan gráf, melyben két csúcs akkor szomszédos, ha legfeljebb két lépés távolságra vannak G-ben.
A gráf félnégyzete a gráf négyzetében a bipartíció egyik felének mondjuk V-nek a feszített részgráfja : csúcshalmaza a V, találkozik egyetlen túra V azon csúcsai között szerepelnek élek, melyek két lépés távolságra vannak G-ben. Ez a félnégyzet egy térképgráf.
Mértanilag úgy is ábrázolható, hogy G-nek megkeressük egy síkba rajzolását, majd V minden csúcsát és a velük szomszédos éleket csillag alakú régióvá növesztjük úgy, hogy ezek a régiók U csúcsaiban érintkezzenek.
Megfordítva, minden térképgráfnak létezik ilyen félnégyzet-reprezentációja.
Ezzel ekvivalens megfogalmazás szerint egy páros síkbarajzolható gráf félnégyzete, melyben az U csúcshalmaz a bipartíció azon fele, mely nem vett részt a félnégyzet-műveletben maximális fokszáma k.
A 3-térképgráfok mind síkbarajzolhatókés minden síkbarajzolható gráfnak van 3-térképgráf reprezentációja.
Navigációs menü
Minden 4-térképgráf 1-síkgráfazaz élenként legfeljebb egy metszésses lerajzolható gráf, és minden optimális 1-síkgráf a sík egy négyszögeléséből minden négyszögű tartományhoz két metsző átló hozzáadásával kapott gráf pedig 4-térképgráf.
A nem optimális 1-síkgráfok azonban nem térképgráfok, mert a térképgráfoktól eltérően tartalmaznak olyan metsző éleket, melyek nem egy 4 csúcsú klikk részei.
Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.