UC Irvine

We study some geographic and geometric graphs namely road networks and clustered graphs from topological viewpoint, i.e., we consider them as embedded graphs, graphs in which the ordering of edges (clockwise or anti-clockwise) incident on each vertex is uniquely defined. A road network is a graph with a vertex at each intersection of roads and an edge for each segment of road between the intersections. A clustered graph is a graph whose vertices belong to properly nested clusters. We present algorithms and models for some problems related to road networks and clustered graphs.

The first problem we consider is how a road network has evolved over time, given two snapshots from different dates. These graph can also have geometric/geographic information, such as the GPS coordinates of some vertices or labels identifying road names. As there can be vertices and edges without such geometric/geographic information, we take a strictly topological approach for the problem. We propose an algorithm, which runs in polynomial time for non degenerate-road networks, and outputs portions of the network that remained intact and also points out added or removed portions. We also analyze our algorithm experimentally taking US road network data from the TIGER/Line archive of the U.S. Census Bureau as input data set and show that our algorithm produces good results in practice.

In the second problem, we study the non-planar properties of road networks. We normally consider road networks as planar graph but they are actually non-planar due to non-intersecting crossings caused by overpass, underpass, or tunnel. We provide a mathematical model of nearly-planar graphs and show that the non-planar graphs that fit this model do have polynomial expansion, i.e., they and all their subgraphs have small separators. We also analyze the Urban Road Network Data set and show that the model is indeed a good fit for non-planar road networks.

Finally, we investigate the C-Planarity problem which asks for drawing of a clustered graph in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for embedded flat clustered graphs, embedded graphs whose clusters partition the vertex set. We provide a subexponential-time algorithm to test C-Planarity for these graphs when the face size is bounded. Further, we also study a variation of tree decomposition in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.