Graph Colouring Algorithm for Validating Labelled 2D Line Drawing Objects
Line labelling has been used to determine whether a two-dimensional (2D) line drawing object is a possible or impossible representation of a three-dimensional (3D) solid object. However, the results are not sufficiently robust because the existing line labelling methods do not have any validation method to verify their own result. In this research paper, the concept of graph colouring is applied to a validation technique for a labelled 2D line drawing. As a result, a graph colouring algorithm for validating labelled 2D line drawings is presented. A high-level programming language, MATLAB R2009a, and two primitive 2D line drawing classes, prism and pyramid are used to show how the algorithms can be implemented. The proposed algorithm also shows that the minimum number of colours needed to colour the labelled 2D line drawing object is equal to 3 for prisms and for pyramids, where n is the number of vertices (junctions) in the pyramid objects.
Keywords: Graph colouring, line labelling, line drawing, validation
Download Full-Text
ABOUT THE AUTHORS
M.Z. Matondang
A PhD student in computer science Universiti Teknologi Malaysia, Johor – Malaysia. He holds Master degree also in computer science from the same University in 2009 and Bachelor degree in mathematics from the Universitas Sumatera Utara, Medan, Indonesia in 2005. His researches interests are in operational research, soft computing and also in mathematical modeling.
A.A.Samah
A. A. Samah has received the Diploma and B.Sc. degree from University of Technology Malaysia in 1991and 1993 respectively. In 1996, she obtained her M.Sc. from the University of Southampton, UK and recently in 2010, she received her PhD from Salford university, UK. Currently she is a lecturer in Faculty of Comp. Science and Information System, University of Technology Malaysia. Her research interests encompass Image Processing, Soft Computing Techniques and Operational and Simulation Modeling.
H. Haron
H. Haron has received the Dip, B.Sc. degree and PhD from University of Technology Malaysia in 1987, 1989 and 2004 respectively. He was awarded M.Sc. from the University of Brighton, UK in 1995. Currently he is an Associate Professor in Faculty of Comp. Science and Information System, University of Technology Malaysia. His research interests include Image Processing and Computer Aided Geometric Design
H. A. Majid
H. A. Majid has received the Dip and B.Sc. degree from University of Technology Malaysia in 1993 and 1995 respectively. In 1998, he obtained his M.Sc. from the University of Salford, UK. Currently he is a lecturer in Faculty of Comp. Science and Information System, University of Technology Malaysia. His research interests focused on Image Processing, Operations Management and, Warranty and Maintenance
M.Z. Matondang
A PhD student in computer science Universiti Teknologi Malaysia, Johor – Malaysia. He holds Master degree also in computer science from the same University in 2009 and Bachelor degree in mathematics from the Universitas Sumatera Utara, Medan, Indonesia in 2005. His researches interests are in operational research, soft computing and also in mathematical modeling.
A.A.Samah
A. A. Samah has received the Diploma and B.Sc. degree from University of Technology Malaysia in 1991and 1993 respectively. In 1996, she obtained her M.Sc. from the University of Southampton, UK and recently in 2010, she received her PhD from Salford university, UK. Currently she is a lecturer in Faculty of Comp. Science and Information System, University of Technology Malaysia. Her research interests encompass Image Processing, Soft Computing Techniques and Operational and Simulation Modeling.
H. Haron
H. Haron has received the Dip, B.Sc. degree and PhD from University of Technology Malaysia in 1987, 1989 and 2004 respectively. He was awarded M.Sc. from the University of Brighton, UK in 1995. Currently he is an Associate Professor in Faculty of Comp. Science and Information System, University of Technology Malaysia. His research interests include Image Processing and Computer Aided Geometric Design
H. A. Majid
H. A. Majid has received the Dip and B.Sc. degree from University of Technology Malaysia in 1993 and 1995 respectively. In 1998, he obtained his M.Sc. from the University of Salford, UK. Currently he is a lecturer in Faculty of Comp. Science and Information System, University of Technology Malaysia. His research interests focused on Image Processing, Operations Management and, Warranty and Maintenance
