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

Md.  Saidur RAHMAN; Noritsugu EGI; Takao NISHIZEKI

doi:10.1093/ietisy/e88-d.1.23

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

Md. Saidur RAHMAN, Noritsugu EGI, Takao NISHIZEKI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.23-30

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.23

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Md. Saidur RAHMAN, Noritsugu EGI, Takao NISHIZEKI, "No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 23-30, January 2005, doi: 10.1093/ietisy/e88-d.1.23.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.23/_p

Copy

@ARTICLE{e88-d_1_23,
author={Md. Saidur RAHMAN, Noritsugu EGI, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs},
year={2005},
volume={E88-D},
number={1},
pages={23-30},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e88-d.1.23},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 23
EP - 30
AU - Md. Saidur RAHMAN
AU - Noritsugu EGI
AU - Takao NISHIZEKI
PY - 2005
DO - 10.1093/ietisy/e88-d.1.23
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - 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.
ER -