No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs (Extended Abstract)

Rahman, Md. Saidur and Egi, Noritsugu and Nishizeki, Takao (2004) No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs (Extended Abstract). In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 387-392(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_36).

Full text not available from this repository.

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 subdividions 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_36
Classifications: M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/468

Actions (login required)

View Item View Item