Recently, randomly wired neural networks (RWNNs) using random graphs for convolutional neural network (CNN) construction have shown efficient layer connectivity but may limit depth, affecting approximation, generalization, and robustness. In this work, we increase the depth of graph-structured CNNs while maintaining efficient pathway usage, which is achieved by building a feature-extraction backbone with a depth-first search, employing edges that have not been traversed for parameter-efficient skip connections. The proposed efficiently pathed deep network (EPDN) reaches maximum graph-based architecture depth without redundant node use, ensuring feature propagation with reduced connectivity. The deep structure of EPDN, coupled with its efficient pathway usage, allows for a nuanced feature extraction. EPDN is highly beneficial for processing remote sensing images, as its performance relies on the ability to resolve intricate spatial details. EPDN facilitates this by preserving low-level details through its deep and efficient skip connections, allowing for enhanced feature extraction. Additionally, the remote-sensing-adapted EPDN variant is akin to a special case of a multistep method for solving an ordinary differential equation (ODE), leveraging historical data for improved prediction. EPDN outperforms existing CNNs in generalization and robustness on image classification benchmarks and remote sensing tasks. The source code is publicly available at https://github.com/AnonymousGithubLink/EPDN.