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

Md. Saidur RAHMAN
Noritsugu EGI

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

Full Text: PDF>>
Buy this Article

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.