Title :
Orthogonal point-set embeddings of 3-connected and 4-connected planar graphs
Author :
Chowdhury, Md Emran ; Rahman, Md Saidur
Author_Institution :
Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
Abstract :
An orthogonal point-set embedding of a planar graph G on a set S of points in Euclidean plane is a drawing of G where each vertex of G is placed on a point of S, each edge is drawn as a sequence of alternate horizontal and vertical line segments and any two edges do not cross except at their common end. In this paper, we devise an algorithm for orthogonal point-set embedding of 3-connected cubic planar graphs having a hamiltonian cycle with at most (5n over 2 + 2) bends, where n is the number of vertices in G. We also give an algorithm for finding an orthogonal point-set embedding of 4-connected planar graphs with at most 6n bends. Both the algorithms run in linear time. To the best of our knowledge this is the first work on orthogonal point-set embeddings with fewer bends.
Keywords :
computational geometry; graph theory; 3 connected cubic planar graphs; 3-connected planar graphs; 4-connected planar graphs; Euclidean plane; hamiltonian cycle; horizontal line segments; orthogonal point set embeddings; vertical line segments; USA Councils; Algorithm; Fewer bends; Orthogonal drawing; Point-set embedding;
Conference_Titel :
Computer and Information Technology (ICCIT), 2011 14th International Conference on
Conference_Location :
Dhaka
Print_ISBN :
978-1-61284-907-2
DOI :
10.1109/ICCITechn.2011.6164808