论文标题
绘制高度较小的Halin-graphs
Drawing Halin-graphs with small height
论文作者
论文摘要
在本文中，我们研究了如何绘制Halin-Graphs，即由树$ t $组成的平面图和该树叶子之间的周期。根据众所周知的图形参数，基于绘画算法和路径宽$ pw（t）$，我们在o（\ log n）$中找到高度的poly-line图纸。我们还为直线图提供了一种算法，并最多可以达到$ 12pw（t）+1 $ $ 1 $ $ $，如果Halin-Graph是立方体，则更小。我们表明，在最坏的情况下，我们的算法达到的高度是最佳的（即，对于某些哈林图）。
In this paper, we study how to draw Halin-graphs, i.e., planar graphs that consist of a tree $T$ and a cycle among the leaves of that tree. Based on tree-drawing algorithms and the pathwidth $ pw(T) $, a well-known graph parameter, we find poly-line drawings of height at most $6pw(T)+3\in O(\log n)$. We also give an algorithm for straight-line drawings, and achieve height at most $12pw(T)+1$ for Halin-graphs, and smaller if the Halin-graph is cubic. We show that the height achieved by our algorithms is optimal in the worst case (i.e. for some Halin-graphs).
