Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Orthogonal Drawings of Plane Graphs without Bends
Extended Abstract

Md. Saidur RahmanContact Information, Mahmuda NazninContact Information and Takao NishizekiContact Information

(7)  Department of computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), 1000 Dhaka, Bangladesh
(8)  Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, 980-8579 Sendai, Japan
Abstract
In an orthogonal drawing of a plane graph G each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A point at which the drawing of an edge changes its direction is called a bend. Every plane graph of the maximum degree at most four has an orthogonal drawing, but may need bends. A simple necessary and sufficient condition has not been known for a plane graph to have an orthogonal drawing without bends. In this paper we obtain a necessary and sufficient condition for a plane graph G of the maximum degree three to have an orthogonal drawing without bends. We also give a linear-time algorithm to find such a drawing of G if it exists.

Keywords  Graph - Algorithm - Graph Drawing - Orthogonal Drawing - Bend


Contact Information Md. Saidur Rahman
Email: saidur@cse.buet.edu

Contact Information Mahmuda Naznin
Email: papri@cse.buet.edu

Contact Information Takao Nishizeki
Email: nishi@ecei.tohoku.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb15
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)