Because of urbanisation, more than 50% of the global population now lives in cities, a number that is ever-increasing. This leads to a need for more dense and complex building constructions, driven by the fact that people are living increasingly close to one another. These structures are often so large that it becomes difficult to navigate in the environment without any assistance. Especially for people with restricted mobility, such as wheelchair users, or the blind or partially sighted, it can pose a challenge to find the best path in a building. Consequently there is a need for navigation graphs that provide a way to structure connectivity information and routes in an indoor environment. Existing methods generally obtain information on the location of various rooms, corridors and their interconnectivity from 2D floor plans or 3D building models. However, these plans and models often were created by the architect when the building was planned, but never updated with new information after the building was built and came into use. Manually updating them is very labour-intensive. Therefore, in this research a method is developed for obtaining a navigation graph from an indoor environment by automatically extracting the information needed from a point cloud. The navigation graph is modelled according to the Open Geospatial Consortium (OGC) standard IndoorGML, which provides a basic structure for indoor navigation. The point clouds used in this research are gathered with a hand-held Mobile Laser Scanner (MLS), which also saves the path (trajectory) taken in the building. This all leads to the main research question: How can a navigation network in IndoorGML format automatically be extracted from a cluttered indoor point cloud and its trajectory? In order to answer this question this research focuses on the detection of doorways, and how they connect indoor spaces, such as rooms and corridors. A new way of door detection is proposed, which is based on the identification of walls using the 3D Medial Axis Transform (MAT) of the point cloud. After this it is explored how the established connectivity relationships can be extended with accessibility information, such as the location of stairs, and the dimensions of doors. Additionally it is researched how a more detailed navigation graph can be created by subdividing large spaces that have multiple connections. In this thesis it is proven that geometric input for a navigation graph can automatically be obtained from a point cloud. 100% of doors could be detected in the dataset that the methods were developed on, and when testing the methods on another point cloud, this number decreased to 70% , due to unforeseen situations. All spaces connected by detected doors, stairways and sloped surfaces were included in the graph, from which a more extensive navigation graph could be produced by subdividing corridors. This final product was compared to networks drawn by humans on a corresponding floor plan, from which it can be concluded that the graph produced by the methodology of this thesis is a good basis for a navigation.