What I'm looking for: A good text on graph data structures, algorithms, and their complexity - aimed at those interested in mathematics research (as opposed to, say, programmers).
List of things a recommendation should have: (not all necessary, but the more the merrier).
- Data structures for representing a graph, and how quickly these can be queried. I'm particularly interested in plane graphs and polyhedra.
- How quickly various elementary operations like finding intersections of subgraphs and other basic things can be done (my current confidence with these things is currently very low, so this point is unfortunately important).
- A reasonable sample of algorithms for solving `standard problems' (eg: planarity testing, finding maximum independent sets, finding plane embeddings, computing standard parameters like connectivity) - and analysis of their complexity.
Context: I'm currently working with cuts of planar graphs. The proof of one of the big results is rather algorithmic (it demonstrates the existence of a certain kind of cutset by finding one explicitly) - and seems to do so rather efficiently in practice. Tragically, I haven't touched complexity in years and would like to brush up on the relevant bits before making grand claims about doing nontrivial things in linear time. I'm finding myself asking lots of questions that I'm sure are very simple (like `how long does it take to check if this vertex is on the boundary of a particular face'). None-the-less, I have encountered these things before: rigor and detail are important for my current needs - ease of reading is not.