  A transitive graph is 2-dimensional if it can be represented as the
intersection of two linear orders. Such representations make answering of
reachability queries trivial, and allow many problems that are NP-hard on
arbitrary graphs to be solved in polynomial time. One may therefore be
interested in finding 2-dimensional graphs that closely approximate a given
graph of arbitrary order dimension.
  In this paper we show that the maximal 2-dimensional subgraphs of a
transitive graph G are induced by the optimal near-transitive orientations of
the complement of G. The same characterization holds for the maximal
permutation subgraphs of a transitively orientable graph. We provide an
algorithm that enables this problem reduction in near-linear time, and an
approach for enlarging non-maximal 2-dimensional subgraphs, such as trees.
