A trackl egy gráf beágyazása egy síkra oly módon, hogy minden él Jordan-görbe , és minden élpár egyszer fordul elő. Az élek találkozhatnak egy közös végponton, vagy ha nincs közös végpontjuk, akkor a belső pontokon. Ez utóbbi esetben a kereszteződésnek keresztirányúnak kell lennie [1] .
Lineáris nyomvonal – egyenes szakaszokkal megrajzolt nyomvonal. Erdős Pál felfedezte szerint egyetlen lineáris nyomvonalnak nincs több éle, mint csúcsa. Erdős észrevette, hogy ha egy v csúcs három vagy több vw , vx és vy élhez kapcsolódik egy lineáris nyomvonalban, akkor ezen élek legalább egyike a másik két élt elválasztó egyenesen fekszik. Az általánosság elvesztése nélkül feltételezzük, hogy vw egy ilyen él , és az x és y pontok a vw egyenes által határolt zárt félterek ellentétes oldalán fekszenek. Ekkor a w csúcsnak elsőfokúnak kell lennie , mivel a vw -n kívül egyetlen más élnek semlehet közös pontja a vx -el és a vy -vel is . A w eltávolításaa nyomkövetésből kisebb nyomkövetést eredményez anélkül, hogy megváltoztatná az élek és a csúcsok száma közötti különbséget. Másrészt, ha bármely csúcsnak legfeljebb két szomszédja van, akkor a kézfogási lemma alapján az élek száma nem haladja meg a csúcsok számát [2] . Erdős bizonyítása alapján megállapítható, hogy bármely vonalas nyomvonal álerdő . Bármely páratlan hosszúságú ciklus átalakítható lineáris nyomkövetéssé, de páros hosszúságú ciklusoknál ez nem lehetséges, mert ha tetszőleges élt választunk, akkor ennek az élnek az ellenkező oldalán felváltva kell más csúcsoknak feküdniük.
Micha Perles egy másik egyszerű bizonyítékkal szolgált arra vonatkozóan, hogy egy lineáris nyomvonalnak legfeljebb n éle van, azon a tényen alapulva, hogy egy lineáris nyomvonalban minden élnek van egy olyan végpontja, ahol az összes él azon a szögön belül van, legfeljebb 180°-os, amelynél az adott él a kezdőbetű (az óramutató járásával megegyező irányban nézve). Ha ez nem így van, akkor két élnek kell lennie, amelyek az él átellenes végpontjaira esnek, és annak a vonalnak az ellenkező oldalán fekszenek, amelyen az él fekszik. Ezek az élek nem metszik egymást, de ez csak egy csúcshoz szomszédos éleknél lehetséges [3] .
Erdős azt is észrevette, hogy annak a pontpárnak a halmazának, ahol a ponthalmaz átmérőjét elérjük, egy lineáris nyomvonalnak kell lennie - két átmérőnek nem lehet közös pontja, mivel ezeknek az átmérőknek a négy vége között két pontnak kell lennie. átmérőjénél nagyobb távolságra. Emiatt a síkban bármely n pontból álló halmaz legfeljebb n átmérőpárt tartalmazhat, ami megválaszolja Heinz Hopf és Erica Panwitz [4] 1934-ben feltett kérdését . Andrew Vashoni korlátokat sejtett a magasabb dimenziókban lévő átmérőpárok számáról, általánosítva ezzel a problémát [2] .
A számítási geometriában egy forgó tolómérő használható lineáris nyomvonal létrehozására bármely konvex helyzetben lévő ponthalmazból a pontok konvex héját érintő párhuzamos vonalak által támogatott pontpárok összekapcsolásával . Ez a grafikon részgráfként átmérős pontok nyomvonalát tartalmazza [5] . A lineáris nyomvonalak számbavételével megoldható a legnagyobb egységátmérőjű sokszög , vagyis az átmérőjéhez viszonyított legnagyobb területű n -szög megtalálása [6] .
John Conway úgy sejtette, hogy egyetlen nyomvonalban sem haladja meg a csúcsok számát az élek száma. Conway maga használta a paths (paths) és spots (spots) kifejezéseket ( az élek és csúcsok helyett ).
Ezzel egyenértékűen a sejtés újrafogalmazható, mivel bármely nyomvonal pszeudoerdő . Pontosabban, ha a nyomkövetési sejtés helyes, a reklámok tulajdonjogát pontosan kifejezhetjük Woodall eredményével – ezek olyan pszeudoerdők, amelyeknek nincs 4 hosszúságú ciklusuk, és van legalább egy páratlan ciklusuk [1] [7] .
Bebizonyosodott, hogy a C 4 kivételével minden ciklikus gráfban van nyomkövetés, ami azt mutatja, hogy a sejtés szigorú abban az értelemben, hogy vannak olyan nyomvonalak, ahol a csúcsok száma megegyezik az élek számával. A másik szélsőséges eset, amikor a csúcsok száma kétszerese az élek számának, szintén elérhető.
Ismeretes, hogy a sejtés igaz azokra a nyomvonalakra, amelyeket úgy rajzolnak meg, hogy bármely él x -monoton görbe, amely legfeljebb egyszer metszi egymást bármely függőleges vonallal [3] .
Lovas, Pach és Szegedy [8] bebizonyította, hogy bármely kétrészes nyomvonal síkgráf , bár nem sík formában van megrajzolva [1] . Következményként kimutatták, hogy bármely n csúcsú trekle-reprezentálható gráfnak legfeljebb 2n − 3 éle van. Azóta a határt kétszer javították. Először 3( n − 1)/2 -re javították [9] , és az utolsó ismert korlát körülbelül 1,428 n [10] . Ezenkívül az eredmény megszerzésére használt módszer bármely ε > 0 esetén egy véges algoritmust ad, amely vagy javítja az (1 + ε) n -hez való kötöttséget, vagy megcáfolja a sejtést.
Ismeretes, hogy ha a sejtés hamis, akkor a minimális ellenpélda egy páros cikluspár lenne, amelyeknek közös csúcsa van [7] . Így a sejtés bizonyításához elegendő annak bizonyítása, hogy az ilyen típusú gráfok nem rajzolhatók nyomvonalként.