Good spanning trees in graph drawing

• Introduces a good spanning tree of a plane graph.
• Solves two open problems on monotone drawings using good spanning trees.
• Finds a 2-visibility drawing of a planar graph using a good spanning tree.
• Gives algorithms to find an spike-VPG and T-shaped drawings of a planar graph.

A plane graph is a planar graph with a fixed planar embedding. In this paper we define a special spanning tree of a plane graph which we call a good spanning tree. Not every plane graph has a good spanning tree. We show that every connected planar graph has a planar embedding with a good spanning tree. Using a good spanning tree, we show that every connected planar graph G of n   vertices has a straight-line monotone grid drawing on an O(n)×O(n2)O(n)×O(n2) grid, and such a drawing can be found in O(n)O(n) time. Our results solve two open problems on monotone drawings of planar graphs posed by Angelini et al. Using good spanning trees, we also give simple linear-time algorithms for finding a 2-visibility representation of a connected planar graph G of n   vertices on a (2n−1)×(2n−1)(2n−1)×(2n−1) grid and for finding a spike-VPG representation of G   on a (2n−1)×n(2n−1)×n grid.