A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
复制标题
平面图真框矩形图的简单线性时间算法
DOI：
10.1006/jagm.2001.1161
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Xin He
中科院分区：
文献类型：
--
作者：
Xin He
本文介绍了平面图形G的一种新的画法，即固有框矩形（PBR）画法。它被定义为G的绘图，这样每个顶点都绘制为矩形，称为框，每个边缘都绘制为水平线或垂直线段，每个面都绘制为矩形。我们建立了G具有PBR图的充分必要条件。我们也给出了一个简单的线性时间算法来寻找这样的图。PBR图与Rahman、Nakano和Nishizeki等人定义的盒子矩形（box -矩形）图密切相关。该方法可为解决BR绘制问题提供一种新的算法。
In this paper we introduce a new drawing style of a plane graph G, called proper box rectangular (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.