No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs

Md. Saidur RAHMAN  Noritsugu EGI  Takao NISHIZEKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.23-30
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
planar graph,  algorithm,  graph drawing,  orthogonal drawing,  bend,  

Full Text: PDF(319.6KB)
>>Buy this Article


Summary: 
A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.