For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs
Md. Saidur RAHMAN Noritsugu EGI Takao NISHIZEKI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
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>>
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.