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 |
|