Χαρακτηριστικό στοιχείο στον χάρτη των Γρηγοριανών αποτελεί ο ασφαλτοστρωμένος επαρχιακός περιφερειακός δρόμος (με πλάτος που κυμαίνεται στα 3 μέτρα) ο οποίος ορίζει ταυτόχρονα και το τοπικό οδικό δίκτυο σχηματίζοντας μια «αγκαλιά» προς το νότο, μέσα και έξω από την οποία αναπτύσσεται ο οικισμός. Ως αφετηρία έχει την Κίσσαμο και ως τέρμα την κοινήτα Πολυρρήνια. Εντός της καμπύλης, οι κατοικίες επικοινωνούν μεταξύ τους με βαθμιδωτά χωμάτινα μονοπάτια, δύο εκ των οποίων οδηγούν σε αδιέξοδο, ενώ το τρίτο αποτελεί τόξο του καμπύλου δρόμου. Εξωτερικά της, σε τρία σημεία, φαίνεται να υπάρχουν χωμάτινες διακλαδώσεις αναπτυσσόμενες ακτινωτά, που οδηγούν προς τα χωράφια.
Στο Παλαιόκστρο παρατηρούμε ότι δεν υπάρχει οδικό δίκτυο εκτός από τον περιφερειακό δρόμο από τον οποίο η πρόσβαση πραγματοποιείται μέσω ενός καλντεριμιού. Αξίζει, ακόμα, να σημειωθεί η προσπάθεια των κατοίκων να διατηρήσουν το καλντερίμι, αφού έχουν αναγνωρίσει την ιστορική σημασία του.