DSpace Repository

Good spanning trees in graph drawing

Show simple item record

dc.contributor.author Md. Iqbal, Hossain
dc.contributor.author Md. Saidur, Rahman
dc.date.accessioned 2016-02-01T16:21:06Z
dc.date.available 2016-02-01T16:21:06Z
dc.date.issued 2015-11-15
dc.identifier.uri http://lib.buet.ac.bd:8080/xmlui/handle/123456789/1957
dc.description.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. en_US
dc.publisher Elsevier Science Publishers Ltd. Essex, UK en_US
dc.subject Graph, Algorithms, Good Spanning Trees, en_US
dc.title Good spanning trees in graph drawing en_US
dc.type Journal en_US
dc.pub.crdept Dept. of Computer Science and Engineering (CSE) en_US
dc.pub.dept Dept. of Computer Science and Engineering (CSE) en_US
dc.pub.event Journal of Theoretical Computer Science en_US
dc.contributor.crauthor Md. Iqbal, Hossain


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search BUET IR


Advanced Search

Browse

My Account