Area-efficient planar straight-line drawings of outerplanar graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Ashim Garg ; Adrian Rusu
• 关键词：Area-efficient ; Outerplanar ; Planar ; Straight-line
• 刊名：Discrete Applied Mathematics
• 出版年：2007
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：1 May 2007
• 卷：155
• 期：9
• 页码：1116-1140
• 文件大小：401 K

摘要

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with l170">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml170&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=b75b10f513dfaa532a1920a5027972dc" title="Click to view the MathML source">n vertices admits a planar straight-line grid drawing with l171">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml171&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=aee09bee5373cb8cfd78558f1153cfe9" title="Click to view the MathML source">O(n²) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41–51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138–148]. Unfortunately, there is a matching lower-bound of l172">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml172&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=9b8dd62a0921b00370f0c8974716b653" title="Click to view the MathML source">Ω(n²) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with l173">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml173&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=7e3b94846360e080b9bf788743239bf6" title="Click to view the MathML source">o(n²) area.

In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph l174">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml174&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=6ddfb785b3bf0e823cf577edc4794e4d" title="Click to view the MathML source">G with degree l175">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml175&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=0efae8d343424d0488c66340e24bc9e1" title="Click to view the MathML source">d admits a planar straight-line grid drawing with area l176">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml176&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=63cffc7e6d08a3993726a2c8e4fadb25" title="Click to view the MathML source">O(dn^1.48) in l177">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml177&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=2108c6899cd00b85726cd4ce50e291c7" title="Click to view the MathML source">O(n) time. This implies that if l178">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml178&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=bb617fac04bbf6899de24bc9ce7b6c68" title="Click to view the MathML source">d=o(n^0.52), then l179">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml179&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=216241939df701c80c82ec83da3eabc6" title="Click to view the MathML source">G can be drawn in this manner in l180">le="text-decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4MR7D39-1&_mathId=mml180&_user=10&_cdi=5629&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=4ca65fc9b7b580f569ce85c289efa640" title="Click to view the MathML source">o(n²) area.