It would be permitted - NEC code wise - to have tel. co and power in same trench...maintaining a 6" clearance(? Article #, anyone..or just a "rule of thumb"?)...BUT water and gas lines usually go DEEPER according to their respective codes and standards. Water is generally below the frost line...don't know about gas.
When in doubt, ask the AHJ.
