✦ LIBER ✦

A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs

✍ Scribed by Xin He

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 219 KB
Volume: 40
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2001.1161

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we introduce a new style of drawing 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 M. S.

Ž .

📜 SIMILAR VOLUMES

A linear algorithm for compact box-drawi

A linear algorithm for compact box-drawings of trees

✍ Masud Hasan; Md. Saidur Rahman; Takao Nishizeki 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

A linear time algorithm to check for the

A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph

✍ Jayaram Bhasker; Sartaj Sahni 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 488 KB

A simple linear time algorithm for findi

A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

✍ Glenn K. Manacher; Terrance A. Mankus 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

## Abstract We exhibit an algorithm for finding a maximum independent set (MIS) for __n__ presorted, unweighted circular arcs in time 0(__n__). Unlike previous algorithms, this is achieved by means of trivial postprocessing of the output of a straightforward algorithm for finding an MIS for a set o