Computation of Subgraphs

This chapter deals with algorithms that compute spanning subgraphs, that is they remove some edges from an input graph in order to establish a certain graph property.

Planar subgraphs are used for graph planarization, i.e., in the SubgraphPlanarizer module. Maximal acyclic subgraphs are used by hierarchical drawing algorithms (i.e., rank assignment modules like LongestPathRanking or OptNodeRanking), where an acyclic input graph is required. In the latter case, the input graph is made acyclic by reversing the edges in a maximal acyclic subgraph.