With the increasing demand on train trips, shortages of train services are experienced, especially in the parts of the world where urban development is fierce. Operational measures to improve railway capacity are considered the most economically viable way to tackle the issue. Though of central importance in railway operations, the problem of capacity analysis was never perfectly solved. The famous UIC compression method suggested by the International Union of Railway was studied by its various related aspects, and several shortcomings have been laid bare by publications known to the community. The analytic method adopted in the SLS software family (which is officially used by Deutsche Bahn AG) produces results with and without a ready timetable. However, it is noteworthy that the result is imperfect, which can be told from the fact that two timetables the clearly differ result in the same value of capacity usage. This is due to over-simplification in its defined computational procedure. Stemming from these facts, this thesis intends to pool efforts into improving the method for railway capacity analysis. Firstly, the UIC compression and SLS methods are briefly analyzed from a methodological perspective, which gives the insight on their approximating nature. Secondly, the methods to compute the separation of train paths are studied, and the concrete computational details are given and analyzed, since this is unavoidable for any method to give a complete description of infrastructure utilization by train operations. Then, it becomes clear that the calculation process of UIC compression and SLS methods amounts to formulate a graph in the shorter sections resulting from their respective dividing procedures. In this regard, we see that such a graph for shorter section is a subgraph of the whole section of interest. Finally, heavily capitalizing “Zacken-Lücken-Problem”, an algorithm is given to compute all the required details to formulate such a graph of the whole infrastructure, which is called infrastructure capacity utilization description (ICUD). Based on the produced compressed timetable graph, the consumed capacity is formulated as the length of the critical path of this graph. This gives a graph-theoretic improvement to the existing methods for railway capacity analysis as it includes more details omitted by the existing methods. As previous study of ICUD gives rather full account on the timetable elements when describing the compressed timetable graph, a natural tendency is to study the impact of timetable elements on the ICUD graph or the consumed capacity. Since the optimization problem of train timetable relies as a matter of fact on studying the impact of combinatorial effect of the timetable elements—a similarity of decision and optimization version of computational problems in the theory of computation. Therefore, this thesis carries further to study the impact of timetable element on railway capacity. The general method is based on detecting difference in the critical path when changing the timetable element in it. Since stop pattern has an immerse impact of the outcome consumed capacity and has in fact taken the major portion of consumed capacity in intercity railway networks. This thesis takes stop plan as an example and studies its impact. The main reasoning is that altering a stop plan potentially changes the ICUD graph, which further changes the critical path and results in a different length. This reasoning is obeyed in the main texts. As the same reason per studying the impact of stop plan as example, this thesis further considers the problem of stop planning of intercity railway train scheduling, which is gaining more practical importance due to the increasing operational importance of intercity trains. For intercity lines, all trains operate in the same speed curve within one line section but heterogenous stop pattern. The study on infrastructure capacity utilization description (ICUD) offers the methodology for computing the impact of timetable element. With this knowledge, the case study in chapter 4 made use of so-called “transfer”—a natural idea—to alleviate the capacity consumption for railway infrastructure, and this chapter further evolves this idea for addressing practical scheduling problems, namely the problems of train stop planning for minimal consumed capacity (SPfMCC). We first formulate SPfMCC as a mixed integer linear programming (MILP) model and reformulate it by ICUD as a non-regular 0,1 integer program that is subject to train stop specifications and minimizes the consumed capacity. The consumed capacity, as the objective function, is represented by a signed sum of elements in the critical path of ICUD. Then, this model is decomposed into a 0,1-integer linear programming model of totally unimodular coefficient matrix and a problem of computing the impacts of stop plans. In this way, the method developed in chapter 4 can be directly applied to formalize a combinatorial algorithm based on the one-to-one stop transfer between different trains. Theoretical analysis and practical computations show that this algorithm returns an improved feasible solution in polynomial time. In addition, we consider two related problems of the similar kind—extensions one and two. Extension one predefines the number of stops at unspecified stations for specified trains, and extension two only defines the numbers of trains to stop at unspecified stations. Eventually, the main work of this thesis is summarized, and the leading research questions are answered, and some future research directions revealed by this study are discussed.