private void createVirtualNodesAndEdges() {
		int idCounter = 1;
		for(LayoutNode v : graph.getAllVertices()) {
			if(v.getId() >= idCounter) {
				idCounter = v.getId() + 1;
			}
		}
		LayoutNodeFactory vertexFactory = new LayoutNodeFactory(idCounter);
		Set<LayoutEdge> edges = graph.getAllEdges();
		for (LayoutEdge e : edges) {
			
			int labelRank = -1;
			if(!e.getLabel().isEmpty()) {
				labelRank = (e.getSourceVertex().getRank() + e.getTargetVertex().getRank()) / 2;
			}
			
			LayoutNode previousNode = e.getTargetVertex();
			for(int rank = e.getTargetVertex().getRank() + 1; rank <= e.getSourceVertex().getRank(); rank++) {
				LayoutNode virtualNode = null;
				if(rank < e.getSourceVertex().getRank()) {
					if(rank == labelRank) {
						/*
						 * Create a label node.
						 */
						virtualNode = vertexFactory.createVertex();
						virtualNode.setLeftWidth(GraphLayoutParameters.NODE_SEPARATION);
						//FIXME: Set right width and height based on edge label dimensions.
						virtualNode.setRightWidth(graph.getRenderingContext().getTextWidth(e.getLabel()));
						virtualNode.setHeight(graph.getRenderingContext().getTextHeight(e.getLabel()));
						virtualNode.setRank(rank);
						virtualNode.setVirtual(true);
						virtualNode.setLabel(true);
						virtualNode.setLabel("l_" + e.getLabel());
						graph.addVertex(virtualNode);
						if(!this.edgeVirtualVerticesMap.containsKey(e)) {
							this.edgeVirtualVerticesMap.put(e, new HashSet<LayoutNode>()); 
						}
						this.edgeVirtualVerticesMap.get(e).add(virtualNode);
					} else {
						/*
						 * Create a plain virtual node.
						 */
						virtualNode = vertexFactory.createVertex();
						virtualNode.setLeftWidth(GraphLayoutParameters.NODE_SEPARATION/2 + 1);
						virtualNode.setRightWidth(GraphLayoutParameters.NODE_SEPARATION/2 + 1);
						virtualNode.setHeight(1);
						virtualNode.setRank(rank);
						virtualNode.setVirtual(true);
						virtualNode.setLabel("v_" + e.getLabel() + "_" + rank);
						graph.addVertex(virtualNode);
						if(!this.edgeVirtualVerticesMap.containsKey(e)) {
							this.edgeVirtualVerticesMap.put(e, new HashSet<LayoutNode>()); 
						}
						this.edgeVirtualVerticesMap.get(e).add(virtualNode);
					}
				} else {
					virtualNode = e.getSourceVertex();
				}
				
				LayoutEdge virtualEdge = graph.getEdgeFactory().createEdge(virtualNode, previousNode);
				virtualEdge.setVirtual(true);
				virtualEdge.setLabel("");
				virtualEdge.setMinLength(e.getMinLength());
				virtualEdge.setEdgeWeight(e.getEdgeWeight());
				graph.addEdge(virtualEdge);
				previousNode = virtualNode;
			}
		}
		
		graph.removeAllEdges(edges);
	}