
For FullText 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.

NoBend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs
Md. Saidur RAHMAN Noritsugu EGI Takao NISHIZEKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E88D
No.1
pp.2330 Publication Date: 2005/01/01 Online ISSN:
DOI: 10.1093/ietisy/e88d.1.23 Print ISSN: 09168532 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>>
Summary:
A plane graph is a planar graph with a fixed embedding. In a nobend 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 nobend orthogonal drawing if at least one of its plane embeddings has a nobend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a lineartime algorithm to examine whether such a planar graph G has a nobend orthogonal drawing and to find one if G has.


