Egyenes élű síkgráf
Az egyenes élű síkgráf (Planar straight-line graph, PSLG) a számítási geometria területén használatos fogalom egy síkbarajzolható gráf olyan síkba ágyazására, amiben az éleket egyenes szakaszok testesítik meg. A Fáry-tétel (1948) állítása szerint minden síkgráfhoz tartozik ilyen síkba ágyazás.

A számítási geometria területén a PSLG-ket gyakran planar subdivision-nek (kb. síkfelosztások) nevezik, annak feltételezésével, hogy ezek a felosztások sokszög alakúak.

Az olyan egyenes élű síkgráfok, melyeknek nincsenek 1 fokszámú csúcsaik a síkot sokszög alakú régiókra osztják, és fordítva. Az 1 fokszám nélküli csúcsok hiánya számos algoritmust leegyszerűsít, de általában nem lényeges feltétel.

A PSLG-k különböző térképek, akár földrajzi információs rendszerek térképeinek reprezentációjára is szolgálhatnak.

A PSLG-k speciális esetei a háromszögelések (sokszög háromszögekre bontása, ponthalmaz háromszögelése). A ponthalmazok háromszögelései maximális egyenes élű síkgráfok abban az értelemben, hogy nem lehetséges egyenes élekkel kiegészíteni őket. A háromszögeléseknek különböző területeken számos felhasználásuk létezik.

Az egyenes élű síkgráfok felfoghatók speciális euklideszi gráfokként is. Az euklideszi gráfok tárgyalásakor azonban főként a metrikus tulajdonságokkal, pl. a csúcsok közötti távolságokkal szokás foglalkozni, míg az egyenes élű síkgráfoknál főleg a topologikus tulajdonságokkal. Egyes gráfoknál, például a Delaunay-háromszögelések esetében a metrikus és topologikus tulajdonságok is fontosak lehetnek.

PSLG-vel kapcsolatos problémák
Pont helyzete. Adott pont esetében kíváncsiak vagyunk, a PSLG melyik tartományához tartozik.
Térképek átfedése. Keressük meg két PSLG (térkép) átfedését, ami a sík felosztása két egyszerre beágyazott PSLG-vel. A térinformatikában ezt a problémát „tematikus térképek átfedésének” nevezik.

Kapcsolódó szócikkek
Kétszeresen összekötött élek listája (Doubly connected edge list, DCEL), a PSLG-k tárolására használt adatstruktúra
Local feature size

Jegyzetek

Geometriai algoritmusok
Geometriai gráfok
Síkgráfok
Az egyenes élű síkgráf ( Planar straight-line graph , PSLG ) a számítási geometria területén használatos fogalom egy síkbarajzolható gráf olyan síkba ágyazására , amiben az éleket egyenes szakaszok testesítik meg . A Fáry-tételállítása szerint minden síkgráfhoz tartozik ilyen síkba ágyazás . A számítási geometria területén a PSLG-ket gyakran planar subdivision-nek ( kb. síkfelosztások ) nevezik , annak feltételezésével , hogy ezek a felosztások sokszög alakúak . Az olyan egyenes élű síkgráfok , melyeknek nincsenekfokszámú csúcsaik a síkot sokszög alakú régiókra osztják , és fordítva . Azfokszám nélküli csúcsok hiánya számos algoritmust leegyszerűsít , de általában nem lényeges feltétel . A PSLG-k különböző térképek , akár földrajzi információs rendszerek térképeinek reprezentációjára is szolgálhatnak . A PSLG-k speciális esetei a háromszögelések ( sokszög háromszögekre bontása , ponthalmaz háromszögelése ) . A ponthalmazok háromszögelései maximális egyenes élű síkgráfok abban az értelemben , hogy nem lehetséges egyenes élekkel kiegészíteni őket . A háromszögeléseknek különböző területeken számos felhasználásuk létezik . Az egyenes élű síkgráfok felfoghatók speciális euklideszi gráfokként is . Az euklideszi gráfok tárgyalásakor azonban főként a metrikus tulajdonságokkal , pl. a csúcsok közötti távolságokkal szokás foglalkozni , míg az egyenes élű síkgráfoknál főleg a topologikus tulajdonságokkal . Egyes gráfoknál , például a Delaunay-háromszögelések esetében a metrikus és topologikus tulajdonságok is fontosak lehetnek . PSLG-vel kapcsolatos problémák Pont helyzete . Adott pont esetében kíváncsiak vagyunk , a PSLG melyik tartományához tartozik . Térképek átfedése . Keressük meg két PSLG ( térkép ) átfedését , ami a sík felosztása két egyszerre beágyazott PSLG-vel . A térinformatikában ezt a problémát „ tematikus térképek átfedésének” nevezik . Kapcsolódó szócikkek Kétszeresen összekötött élek listája ( Doubly connected edge list , DCEL ) , a PSLG-k tárolására használt adatstruktúra Local feature size Jegyzetek Geometriai algoritmusok Geometriai gráfok Síkgráfok