The graph is one of the most important abstractions used in computer science. This thesis gives substantial improvements to the state of the art regarding 4 different problems on static or dynamic graphs, namely: Static reachability in planar graphs, Online bipartite matching with recourse, Deterministic fully-dynamic 2-edge connectivity and bridge-finding, and Strong trail orientations of graphs.