diff --git a/src/main/java/net/onrc/onos/ofcontroller/floodlightlistener/RCNetworkGraphPublisher.java b/src/main/java/net/onrc/onos/ofcontroller/floodlightlistener/RCNetworkGraphPublisher.java
index 167583f..156ee1a 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/floodlightlistener/RCNetworkGraphPublisher.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/floodlightlistener/RCNetworkGraphPublisher.java
@@ -14,13 +14,10 @@
 import net.onrc.onos.ofcontroller.core.IOFSwitchPortListener;
 import net.onrc.onos.ofcontroller.linkdiscovery.ILinkDiscoveryListener;
 import net.onrc.onos.ofcontroller.linkdiscovery.ILinkDiscoveryService;
-import net.onrc.onos.ofcontroller.networkgraph.FloodlightToOnosMappers;
 import net.onrc.onos.ofcontroller.networkgraph.INetworkGraphService;
-import net.onrc.onos.ofcontroller.networkgraph.LinkImpl;
-import net.onrc.onos.ofcontroller.networkgraph.NetworkGraph;
-import net.onrc.onos.ofcontroller.networkgraph.NetworkGraphDatastore;
-import net.onrc.onos.ofcontroller.networkgraph.Switch;
-import net.onrc.onos.ofcontroller.util.Dpid;
+import net.onrc.onos.ofcontroller.networkgraph.LinkEvent;
+import net.onrc.onos.ofcontroller.networkgraph.NetworkGraphDiscoveryInterface;
+import net.onrc.onos.ofcontroller.networkgraph.SwitchEvent;
 import net.onrc.onos.registry.controller.IControllerRegistryService;
 
 import org.openflow.protocol.OFPhysicalPort;
@@ -49,36 +46,18 @@
 	private IDatagridService datagridService;
 	private INetworkGraphService networkGraphService;
 
-	private NetworkGraph networkGraph;
-	private NetworkGraphDatastore southboundNetworkGraph;
+	private NetworkGraphDiscoveryInterface networkGraphDiscoveryInterface;
 
 
 	@Override
 	public void linkDiscoveryUpdate(LDUpdate update) {
-
-		// TODO Move this sanity check when retrieving port to common place?
-		Switch srcSw = networkGraph.getSwitch(update.getSrc());
-		if (srcSw == null) {
-			log.error("Switch {} missing when adding Link {}",
-					new Dpid(update.getSrc()), update);
-			return;
-		}
-
-		Switch dstSw = networkGraph.getSwitch(update.getDst());
-		if (dstSw == null) {
-			log.error("Switch {} missing when adding Link {}",
-					new Dpid(update.getDst()), update);
-			return;
-		}
-
-		// XXX Is it correct to add Link object created with networkGraph to southboundNetworkGraph?
-		LinkImpl link = new LinkImpl(networkGraph,
-			srcSw.getPort((long) update.getSrcPort()),
-			dstSw.getPort((long) update.getDstPort()));
-
+		LinkEvent linkEvent = new LinkEvent(update.getSrc(), 
+				(long)update.getSrcPort(), update.getDst(), 
+				(long)update.getDstPort());
+		
 		switch (update.getOperation()) {
 		case LINK_ADDED:
-//			southboundNetworkGraph.addLink(link);
+			networkGraphDiscoveryInterface.putLinkEvent(linkEvent);
 			/*
 			TopologyElement topologyElement =
 					new TopologyElement(update.getSrc(),
@@ -93,7 +72,7 @@
 			// We never use it.
 			break;
 		case LINK_REMOVED:
-//			southboundNetworkGraph.removeLink(link);
+			networkGraphDiscoveryInterface.removeLinkEvent(linkEvent);
 			/*
 			TopologyElement topologyElement =
 					new TopologyElement(update.getSrc(),
@@ -127,8 +106,8 @@
 			return;
 		}
 
-		Switch onosSwitch = FloodlightToOnosMappers.map(networkGraph, sw);
-//		southboundNetworkGraph.addSwitch(onosSwitch);
+		SwitchEvent switchEvent = new SwitchEvent(sw.getId());
+		networkGraphDiscoveryInterface.putSwitchEvent(switchEvent);
 
 		/*
 		// TODO publish ADD_SWITCH event here
@@ -167,8 +146,9 @@
 
 	@Override
 	public void removedSwitch(IOFSwitch sw) {
-		// TODO Auto-generated method stub
-
+		// TODO move to cleanup thread
+		SwitchEvent switchEvent = new SwitchEvent(sw.getId());
+		networkGraphDiscoveryInterface.removeSwitchEvent(switchEvent);
 	}
 
 	@Override
@@ -227,7 +207,6 @@
 		floodlightProvider.addOFSwitchListener(this);
 		linkDiscovery.addListener(this);
 
-		networkGraph = networkGraphService.getNetworkGraph();
-		southboundNetworkGraph = networkGraphService.getSouthboundNetworkGraph();
+		networkGraphDiscoveryInterface = networkGraphService.getNetworkGraphDiscoveryInterface();
 	}
 }
diff --git a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/INetworkGraphService.java b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/INetworkGraphService.java
index cef80ad..318c0f7 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/INetworkGraphService.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/INetworkGraphService.java
@@ -19,5 +19,5 @@
      * applications/modules that shouldn't touch it
      * @return
      */
-    public NetworkGraphDatastore getSouthboundNetworkGraph();
+    public NetworkGraphDiscoveryInterface getNetworkGraphDiscoveryInterface();
 }
diff --git a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphDiscoveryInterface.java b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphDiscoveryInterface.java
new file mode 100644
index 0000000..a4d21a9
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphDiscoveryInterface.java
@@ -0,0 +1,16 @@
+package net.onrc.onos.ofcontroller.networkgraph;
+
+import java.net.InetAddress;
+import java.util.Set;
+
+public interface NetworkGraphDiscoveryInterface {
+	public void putSwitchEvent(SwitchEvent switchEvent);
+	public void removeSwitchEvent(SwitchEvent switchEvent);
+	public void putPortEvent(PortEvent portEvent);
+	public void removePortEvent(PortEvent portEvent);
+	public void putLinkEvent(LinkEvent linkEvent);
+	public void removeLinkEvent(LinkEvent linkEvent);
+	public void updateDeviceEvent(DeviceEvent deviceToUpdate, 
+			Set<InetAddress> updatedIpAddrs, Set<Port> updatedAttachmentPoints);
+	public void removeDeviceEvent(DeviceEvent deviceEvent);
+}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphImpl.java b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphImpl.java
index 14dfd64..539ca63 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphImpl.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphImpl.java
@@ -28,13 +28,17 @@
  * re-ordering. e.g.) Link Add came in, but Switch was not there.
  *
  */
-public class NetworkGraphImpl extends AbstractNetworkGraph {
+public class NetworkGraphImpl extends AbstractNetworkGraph
+								implements NetworkGraphDiscoveryInterface {
 
     private static final Logger log = LoggerFactory
 	    .getLogger(NetworkGraphImpl.class);
+    
+    private final NetworkGraphDatastore datastore;
 
     public NetworkGraphImpl() {
 	super();
+	datastore = new NetworkGraphDatastore(this);
     }
 
     /**
@@ -518,4 +522,113 @@
 	    super(message);
 	}
     }
+
+    /* ******************************
+     * NetworkGraphDiscoveryInterface methods
+     * ******************************/
+    
+	@Override
+	public void putSwitchEvent(SwitchEvent switchEvent) {
+		if (checkAddSwitchInvariant()) {
+			datastore.addSwitch(switchEvent);
+			putSwitch(switchEvent);
+		}
+		// TODO handle invariant violation
+	}
+
+	@Override
+	public void removeSwitchEvent(SwitchEvent switchEvent) {
+		if (checkRemoveSwitchInvariant()) {
+			datastore.deactivateSwitch(switchEvent);
+			removeSwitch(switchEvent);
+		}
+		// TODO handle invariant violation
+	}
+
+	@Override
+	public void putPortEvent(PortEvent portEvent) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void removePortEvent(PortEvent portEvent) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void putLinkEvent(LinkEvent linkEvent) {
+		if (checkAddLinkInvariant()) {
+			datastore.addLink(linkEvent);
+			putLink(linkEvent);
+		}
+		// TODO handle invariant violation
+	}
+
+	@Override
+	public void removeLinkEvent(LinkEvent linkEvent) {
+		if (checkRemoveLinkInvariant()) {
+			datastore.removeLink(linkEvent);
+			removeLink(linkEvent);
+		}
+		// TODO handle invariant violation
+	}
+
+	@Override
+	public void updateDeviceEvent(DeviceEvent deviceToUpdate,
+			Set<InetAddress> updatedIpAddrs, Set<Port> updatedAttachmentPoints) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void removeDeviceEvent(DeviceEvent deviceEvent) {
+		// TODO Auto-generated method stub
+		
+	}
+	
+	/* *****************
+	 * Internal methods to check invariants of the network graph
+	 * *****************/
+	
+	private boolean checkAddSwitchInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkRemoveSwitchInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkAddPortInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkRemovePortInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkAddLinkInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkRemoveLinkInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkAddDeviceInvariant() {
+		// TODO implement
+		return true;
+	}
+	
+	private boolean checkRemoveDeviceInvariant() {
+		// TODO implement
+		return true;
+	}
 }
diff --git a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphModule.java b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphModule.java
index 0824f63..7315f1c 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphModule.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/networkgraph/NetworkGraphModule.java
@@ -19,7 +19,7 @@
 	// private RCNetworkGraphPublisher eventListener;
 	
 	private NetworkGraphImpl networkGraph;
-	private NetworkGraphDatastore southboundNetworkGraph;
+	//private NetworkGraphDatastore southboundNetworkGraph;
 
 	private IRestApiService restApi;
 
@@ -54,7 +54,7 @@
 		restApi = context.getServiceImpl(IRestApiService.class);
 		
 		networkGraph = new NetworkGraphImpl();
-		southboundNetworkGraph = new NetworkGraphDatastore(networkGraph);
+		//southboundNetworkGraph = new NetworkGraphDatastore(networkGraph);
 	}
 
 	@Override
@@ -68,8 +68,8 @@
 	}
 
 	@Override
-	public NetworkGraphDatastore getSouthboundNetworkGraph() {
-		return southboundNetworkGraph;
+	public NetworkGraphDiscoveryInterface getNetworkGraphDiscoveryInterface() {
+		return networkGraph;
 	}
 
 }