Good spanning trees in graph drawing

Abstract

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 ( n 2 ) grid, and such a drawing can be found in 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 ( 2 n - 1 ) × ( 2 n - 1 ) grid and for finding a spike-VPG representation of G on a ( 2 n - 1 ) × n grid.