Excellent, thank you! I think I am more familiar with the other meaning of layered graph drawing - it would have never occurred to me to search for that. I'm not too concerned about finding the absolute minimum number of crossings, so I think I should be able to avoid any NP-hardness. Anyway, I appreciate it.

Yes, they reflect the structure of the graph - to be specific, the x axis is time. The graph currently has about 86 nodes and 74 edges, but it will be growing. I estimate a total for both nodes and edges somewhere between 400 and 500.