|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
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.2KB)
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.
|
|
