SIAM Journal on Computing · 1998 · 85 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationGraph AlgorithmsGraph DrawingGraph Layout AlgorithmsGraph TheoryGraph Drawing AlgorithmsOrthogonal Graph DrawingPlanar Graph AlgorithmsPlanar Graph DrawingPlanar GraphsPolynomial Time ComplexityPolynomial-time Algorithms
We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NP-complete in the general case. In this paper we introduce and study the new concept of spirality, which is a measure of how an orthogonal drawing is "rolled up," and develop a theory on the interplay between spirality and number of bends of orthogonal drawings. We exploit this theory to present polynomial time algorithms for two significant classes of graphs: series-parallel graphs and 3-planar graphs. Series-parallel graphs arise in a variety ofproblems such as scheduling, electrical networks, data-flow analysis, database logic programs, and circuit layout. Also, they play a central role in planarity problems. Furthermore, drawings of 3-planar graphs are a classical field of investigation.
22
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
John E. Hopcroft, Robert E. Tarjan · Journal of the ACM · 1974 · 1.1K citations · Full text
Algorithms for drawing graphs: an annotated bibliography
Giuseppe Di Battista, Peter Eades, Roberto Tamassia et al. · Computational Geometry · 1994 · 860 citations