The classification of 3d point cloud data is an important component of applications such as map generation and architectural modeling. However, the complexity of the scenes together with the level of noise in the data acquired through mobile laser range-scanning make this task quite difficult. We propose a novel classification method that relies on a combination of edge, node, and relative density information within an Associative Markov Network framework. The main application of our work is the classification of the structures within a point cloud into curvilinear, surface-like, and noise components. We are able to robustly extract complicated structures such as tree branches. The measures taken to ensure the robustness of our method generalize and can be leveraged in noise reduction applications as well. We compare our work with another state of the art classification technique, namely Directional Associative Markov Network, and show that our method can achieve significantly higher accuracy in the classification of the 3d point clouds.